浙大数据结构：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)
{ //全都小于0
cout << "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;
}