题目描述

给定一个包含 K 个整数的序列 {N1,N2,…,NK}。

连续子序列定义为 {Ni,Ni+1,…,Nj}，其中 1≤i≤j≤K。

最大子序列是指序列内各元素之和最大的连续子序列。

例如，给定序列 {−2,11,−4,13,−5,−2}，它的最大子序列为 {11,−4,13}，其各元素之和为 20。

现在你需要求出最大子序列的各元素之和，并且输出最大子序列的第一个元素和最后一个元素的值。

输入格式
第一行包含一个整数 K。

第二行包含 K 个整数。

输出格式
输出一行三个整数，分别表示最大子序列的各元素之和以及最大子序列的第一个元素和最后一个元素的值。

设最大子序列为 {Ni,Ni+1,…,Nj}，如果答案不唯一，则选择 i 更小的解，如果仍不唯一，则选择 j 更小的解。

注意，我们规定，如果所有 K 个数字均为负数，则其最大和定义为 0，并且应该输出整个序列的第一个数字和最后一个数字。

数据范围
1≤K≤10000,
序列内元素的绝对值不超过 105。

样例

输入样例：

10
-10 1 2 3 4 -5 -23 3 7 -21

输出样例：

10 1 4

算法

(动态规划) $O(n)$

#include <iostream>
using namespace std;

const int N = 1e4 + 10;


int main() {
    int a[N], s[N], q[N], hh = 0, tt = -1, n, m, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++) {
        s[i] = s[i - 1] + a[i];
    }


    // s[l..r] = s[r] - s[l-1];
    // max(s[l..r]) = max(s[r] - s[l-1]);
    int l, r;
    q[++ tt] = s[0];
    for (int i = 1; i <= n; i ++) {
        int sum = s[i] - s[q[hh]];
        if (i == 1 || ans < sum) {
            ans = sum;
            l = q[hh] + 1;
            r = i;
        }
        while (hh <= tt && s[q[tt]] > s[i]) {
            tt --;
        }
        q[++ tt] = i;
    }

    if (ans < 0) {
        cout << 0 << " " << a[1] << " " << a[n];
    } else {
        cout << ans << " "<< a[l] << " "<< a[r] << endl;    
    }

    return 0;
}

时间复杂度 $O(n)$