题解 | 最大连续子序列

#include <stdio.h>
#include <algorithm>
#include <limits>
int dp[10002];
using namespace std;
int main() {
    int k;
    while (scanf("%d", &k) != EOF) {
        if (k == 0) {
            break;
        }
        int data[k];
        bool isallnegative = true; //是否所有的数都为负数？
        for (int i = 0 ; i < k ; i++) {
            scanf("%d", &data[i]);
            if (data[i] >= 0) {
                isallnegative = false; //出现了正数
            }
        }
        if (isallnegative) { //所有输入的数均为负数
            printf("0 %d %d\n", data[0], data[k - 1]);
            continue;
        }
        dp[0] = 0;//初始化长度为0的序列和为0
        int t = 0;
        int first, final =
            0; //记录最大的和的连续子序列的起始下标和最终下标
        int max_len = numeric_limits<int>::min();
        for (int i = 1 ; i <= k ;
                i++) { //构建所有问题问题子规模的答案1-k（i为长度非下标）
            if (dp[i - 1] > 0) { //延续了之前序列 长度为i-1的子序列和大于0
                dp[i] = dp[i - 1] + data[i - 1]; //i-1本身作为子序列的终点下标
            } else { //长度为i-1的子序列和小于或者等于0-->新起了一段子序列
                dp[i] = data[i - 1];
                //更新数组的起始下标要减1
                // 因为i的取值范围是1-k 包含了k i代表的是长度非下标
                t = i - 1;
            }
            //更新最大连续子序列和的最大值及其起始和终点的下标
            if (dp[i] > max_len) {
                max_len = dp[i];
                first = t;
                final = i - 1; //下标要-1
            }
        }
        printf("%d %d %d\n", max_len, data[first], data[final]);
    }
    return 0;
}