dp[i]:以i为结尾的最大连续子列和
dp[i] = max(dp[i - 1] + a[i], a[i])
边界：dp[0]=a[0]
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 10;
int k, a[maxn], dp[maxn];
int main()
{
scanf("%d", &k);
bool flag = false;
for (int i = 0; i < k; i++)
{
scanf("%d", &a[i]);
if (a[i] >= 0)flag = true;
}
if (flag == false)
{
printf("0 %d %d", a[0], a[k - 1]);
return 0;
}
dp[0] = a[0];
for (int i = 1; i < k; i++)
{
dp[i] = max(dp[i - 1] + a[i], a[i]);
}
int kk = 0;
for (int i = 0; i < k; i++)
{
if (dp[i] > dp[kk])kk = i;
}
int maxsum = dp[kk], start;
for (start = kk; start >= 0; start--)
{
maxsum -= a[start];
if (maxsum == 0)break;
}
printf("%d %d %d", dp[kk], a[start], a[kk]);
return 0;
}
dp[i]:以i为结尾的最大连续子列和
dp[i] = max(dp[i - 1] + a[i], a[i])
边界：dp[0]=a[0]
s[i]:以i为结尾的最大连续子列和的首元素位置序号
for (int i = 1; i < k; i++)
{
if (dp[i - 1] + a[i] > a[i])
{
dp[i] = dp[i - 1] + a[i];
s[i] = s[i - 1];
}
else
{
dp[i] = a[i];
s[i] = i;
}
}
