1007. Maximum Subsequence Sum (25)

 距离PAT考试还有13天,最重要的是做透每一题,以及捡起来贪心回溯动态规划的感觉

(1)思路

动态规划

sum的值为当前子串,maxsum的值为最大子串的值

maxsum=max(sum,maxsum);

需要思考的是如何保存最大子串的index

我们 设置三个变量 fir和last,以及b来保存

b为当前子串的开始,fir,last分别为最终子串的开始和结束

在遍历这个子串的过程中如果当前子串sum的值为负了,那么我们要舍弃当前的子串

因为无论后面怎样,这里的sum都会让后续的值变的更小,我们在sum小于零的时候

让其从新开始记录子串,即赋sum为0,并且令b等于此时的i+1,记录新的子串的起始位置

在sum非负的情况下我们比较当前子串和maxsum的值,如果maxsum更大那什么也不做

否则maxsum更新,此时把当前子串的开始b赋给fir即最终的子串的开始,由于last(最终子串)就是i

也等于当前子串的结束,这也是为什么不用一个变量e来保存结束位置的原因

#include <cstdio>
#include <vector>

using namespace std;

int main() {
  int n;
  scanf("%d",&n);
  
  vector<int> v(n);
  int flag=0;
  for(int i=0;i<n;i++) {
    scanf("%d",&v[i]);
    if(v[i] >= 0) flag=1;
  }
  if(flag == 0) {
    printf("%d %d %d",0,v[0],v[n-1]);
    return 0;
  }
  
  int sum=0,maxsum=-1,b=0,last=n-1,fir=0;
  for(int i=0;i<n;i++) {
    sum+=v[i];
    if(sum < 0) {
      sum=0;
      b=i+1;
    } else {
      if(sum > maxsum) {
    fir=b;
    last=i;
    maxsum=sum;
      }
    }
  }
  printf("%d %d %d",maxsum,v[fir],v[last]);
  return 0;
}

这里暴力不能ac,注意子串包括一个元素的串

#include <cstdio>
#include <climits>
#include <vector>
using namespace std;

int main() {
  int n;
  scanf("%d",&n);
  vector<int> v;
  v.resize(n);
  const int inf=INT_MIN;
  int flag=0;
  for(int i=0;i<n;i++) {
    scanf("%d",&(v[i]));
    if(v[i] >= 0) flag=1;
  }
  if(flag == 0) {
    printf("%d %d %d",0,v[0],v[v.size()-1]);
    return 0;
  }
  int st=0,end=n-1,maxsum=inf;
  for(int i=0;i<n;i++) {
    for(int j=i;j<n;j++) { //得从i开始不能是i+1
      int sum=0;
      for(int k=i;k<=j;k++) {
    sum+=v[k];
      }
      if(sum > maxsum) {
    maxsum=sum;
    st=i;
    end=j;
      }
    }
  }
  printf("%d %d %d",maxsum,v[st],v[end]);
  return 0;
}