浙大数据结构：01-复杂度2 Maximum Subsequence Sum

数据结构MOOC

PTA习题

01-复杂度2 Maximum Subsequence Sum

#include <iostream>
using namespace std;
const int M = 100005;
int a[M];
int main()
{int k;cin >> k;int f = 1;for (int i = 0; i < k; i++){cin >> a[i];if (a[i] >= 0)//如果出现大于0则进行在线处理f = 0;}if (f){  //全都小于0cout << "0" << ' ' << a[0] << ' ' << a[k - 1];return 0;}int s = 0, ma = -1, l = 0, j = 0, r;for (int i = 0; i < k; i++){s += a[i];if (s > ma){  //更新答案ma = s;r = a[i];l = a[j];}if (s < 0){s = 0;j = i + 1;  //因为扔掉了左边，所以答案数组的左指针一定大于i}}cout << ma << ' ' << l << ' ' << r;return 0;
}