题解 | 最大序列和

#include <bits/stdc++.h>
using namespace std;

const int N=1000001;

int a[N];

int main(){
    int n;
    memset(a,0,sizeof(a));
    while(cin>>n){
        int b[n];
        for(int i=0;i<n;i++){
            cin>>b[i];
        }
        for(int i=0;i<n;i++){
            if(i==0)a[i]=b[i];
            else a[i]=max(b[i],a[i-1]+b[i]);
        }
        int ans=a[0];
        for(int i=0;i<n;i++){
            ans=max(ans,a[i]);
        }
        cout<<ans<<endl;
    }
}

这一题可能比前面的动态规划问题难想一点，其实我们可以发现，如果要求最大的子序列长度，只需要根据新加入的字段来判断即可，对于一个长度的字段，那么无论如何，他的最大值就是自身，如果有两个呢？多加一个，求和，比较一下就知道当前的新的最大值，假如这个最大值更小了，就不加上左边的这个最大值，标记为当前最大值为自身即可，如果更大了，就标记为加和，如果是三个呢？三个连续的，就可以发现，前面两个的操作不就是两种可能吗，但是无论如何，他已经生成了前面的最大值，我们接着做一样的操作即可，这样，递归函数不就出来了吗，对于动态规划，改成数组的数列推演即可。