更好的阅读体验：PAT 最大子序和

动态查找

e：子段终点
b：子段起点
btmp：子段临时起点
sum：用来相加找最大值
res：最大值

算法思想

每一轮用sum累加，判断sum与是否比之前确定的res更大，如果是，则更新sum，并且更新起点和终点，如果sum<0了，言外之意就是前面的子段都可以不要了，从i+1下标重新开始（加上前面的负数还不如不加），这时用btmp确定临时起点为i+1

#include <iostream>

using namespace std;

const int N = 10010, INF = 0x3f3f3f3f;

int n, a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];

    int res = -INF, sum = 0, b = 0, e = 0, btmp = 0;
    for (int i = 0; i < n; i ++)
    {
        sum += a[i];
        if (sum > res) e = i, b = btmp, res = sum;
        if (sum < 0) sum = 0, btmp = i + 1;
    }

    if (res < 0) res = 0, b = 0, e = n - 1;
    cout << res <<' '<< a[b] <<' '<< a[e] << endl;

    return 0;
}

附上正规动态规划的算法

状态转移：f[i]=max(f[i-1]+a[i],a[i]);

#include <iostream>

using namespace std;

const int N = 1000010, INF = 0x3f3f3f3f;

int a[N], n;
int f[N];   //以i结尾的最大子序列

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    int res = -INF, b = 1, e = 1, btmp = 1;
    for (int i = 1; i <= n; i ++)
    {
        f[i] = max(f[i - 1] + a[i], a[i]);
        if (f[i - 1] < 0) btmp = i;
        if (res < f[i]) res = f[i], e = i, b = btmp;
    }

    if (res < 0) res = 0, b = 1, e = n;
    cout << res <<' '<< a[b] <<' '<< a[e] << endl;

    return 0;
}