王道机试指南 例题12.2 最大序列和

题目：

算法及思路：

动态规划。

代码：

#include <iostream>
#include <ostream>
#include <algorithm>
using namespace std;

int main() {
    long long n;
    while(cin>>n){
        long long a[n];
        long long dpi[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(i==0) dpi[i]=a[i];
            else{
                dpi[i]=max(dpi[i-1]+a[i],a[i]);
            }
        }
        sort(dpi,dpi+n);
        cout<<dpi[n-1]<<endl;
    }
    return 0;
}

运行结果：