动态规划 | 1007 Maximum Subsequence

1007 Maximum Subsequence Sum
⚠️题目要求最大子序列和<0时，输出的为0 头 尾。
⚠️仅有一个元素的情况、包含0的情况
⚠️dp[i]保存的是 以当前num[I]结尾的最大子序列和
dp[i] = max( dp[i - 1] + num[i], num[i )

#include <cstdio>
#include <algorithm>

#define N 10010
#define INF -0x3f3f3f3f
using namespace std;
int n, num[N];
int dp[N], st[N], ed[N], mmax, ind;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num[i]);
    }
    //init border
    st[0] = ed[0] = dp[0] = num[0];
    for (int j = 1; j < n; ++j) {
        if (dp[j - 1] + num[j] >= num[j]) {
            dp[j] = dp[j - 1] + num[j];
            st[j] = st[j - 1], ed[j] = num[j];
        } else {
            dp[j] = num[j];
            st[j] = ed[j] = num[j];
        }
    }
    mmax = INF;
    for (int k = 0; k < n; ++k) {
        if (dp[k] > mmax) {
            mmax = dp[k];
            ind = k;
        }
    }
    if (mmax >= 0) {
        printf("%d %d %d\n", mmax, st[ind], ed[ind]);
    } else {
        printf("0 %d %d\n", num[0], num[n - 1]);
    }
    return 0;
}

更简洁的思路：https://www.liuchuo.net/archives/2122