PAT 1007 最大子段和——动态规划

当时上课学dp时的一道例题，最优子结构是以第j个（含）结束的子段中和最大的那个（刁钻），记为b[j]，则b[j] = max(b[j-1]+a[j],a[j])。

注意这里最大和有可能是负的，所以maxtmp初始化要为负数而不是0，第五个测试点就是这样。

代码：

#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>

using namespace std;

const int maxn = 100005;
#define INF 0x3f3f3f

int a[maxn],b[maxn],c[maxn];
int K = 0;

int main(){
    cin>>K;
    bool flg = false;
    for(int i = 0;i < K;i++){
        cin>>a[i];
        if(a[i] >= 0) flg = true;
    }
    b[0] = a[0];
    c[0] = 0;
    int maxtmp = -INF,res = 0;
    for(int i = 1;i < K;i++){
        b[i] = max(a[i],b[i-1]+a[i]);
        c[i] = a[i]>b[i-1]+a[i]?i:c[i-1];
        //cout<<b[i]<<" "<<c[i]<<endl;
        if(maxtmp < b[i] || (maxtmp == b[i] && c[i] < c[res])){
            maxtmp = b[i];
            res = i;
        }
    }
    if(flg)
        cout<<b[res]<<" "<<a[c[res]]<<" "<<a[res];
    else
        cout<<0<<" "<<a[0]<<" "<<a[K-1];
}

6ms