最大子列和的问题

原题：https://pintia.cn/problem-sets/15/problems/709 刚开始的时候看到题目想到直接暴力求解将数列的所有子数列求出来然后再找最大值，显然是不行的，肯定超时。然后借鉴了别人的思路： 对于数列{p1}：max1=p1； {p1，p2}：max2=（p2，p1+p2） {p1，p2，p3}：max3=（p3，p2+p3，p1+p2+p3） … {p1,p2,…pn}:maxn=(pn,pn+pn-1…,p1+p2+…+pn)

然后对于 {max1,max2}:MAX=(max1,max2); {max3,MAX}:MAX=(max3,MAX); … {maxn,MAX}:MAX=(maxn,MAX); 最后得出MAX

代码： #include #include using namespace std;

int K;

int main() { vector v; int m; int sum = 0; scanf("%d", &K); for (int i = 0; i < K; i++) { scanf("%d", &m); v.push_back(m); } int max = v[0]; int max1 = v[0]; for (int j = 1; j < K; j++) { for (int i = j; i >= 0; i–) { sum += v[i]; max1 = (max1 > sum) ? max1 : sum; } max = (max > max1) ? max : max1; sum = 0; }

cout << max << endl;

}