最大连续子序列（暑假每日一题 27）

给定 $K$ 个整数的序列 { N 0 , N 1 , … , N K − 1 } \{N_0,N_1,…,N_{K−1}\} {N0​,N1​,…,NK−1​}，其任意连续子序列可表示为 { N i , N i + 1 , … , N j } \{N_i,N_{i+1},…,N_j\} {Ni​,Ni+1​,…,Nj​}，其中 $0\le i\le j<K$。

最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 { − 2 , 11 , − 4 , 13 , − 5 , − 2 } \{−2,11,−4,13,−5,−2\} {−2,11,−4,13,−5,−2}，其最大连续子序列为 { 11 , − 4 , 13 } \{11,−4,13\} {11,−4,13} ，最大和为 $20$。

编写程序得到其中最大子序列的和并输出该子序列的第一个和最后一个元素的下标。

输入格式
输入包含多组测试数据。

每组数据占 $2$ 行，第 $1$ 行给出正整数 $K$。

第 $2$ 行给出 $K$ 个整数 $N_1,\dots ,N_K$。

输出格式
每组数据输出一行结果，包含最大子序列的和以及子序列的第一个下标 $i$ 和最后一个元素的下标 $j$。

所有元素下标为 $0\sim K-1$。

如果最大子序列不唯一，则选择 $i$ 最小的那个子序列，如果仍不唯一，则选择 $i$ 最小的子序列中 $j$ 最小的那个子序列。

若所有 $K$ 个元素都是负数，则定义其最大和为 0，输出 0 0 0。

数据范围
$1\le K\le 10^5,$
$-10000\le N_i\le 10000,$
输入最多包含 $10$ 组数据。

输入样例：

8
6 -2 11 -4 13 -5 -2 10
5
10 -10 10 -10 10
8
-1 -5 -2 3 -1 0 -2 0
4 
-1 -2 -4 -3
1
2
3
4
5
6
7
8

输出样例：

27 0 7
10 0 0
3 3 3
0 0 0
1
2
3
4

---

DP问题

• 状态表示 f[i] 代表以 i 为右端点的区间
• 属性 max
• 状态计算：f[i] = max(w[i], w[i] + f[i - 1])

#include

using namespace std;

const int N = 100010;

int n;
int q[N];

int main(){
    
    while(~scanf("%d", &n)){
        
        for(int i = 0; i < n; i++)
            scanf("%d", &q[i]);
        
        int res = 0, l = 0, r = 0;
        // f 表示以i为左端点的区间最大连续和
        // g 表示以i为左端点的区间最大连续和对应的最左边的区间右端点
        for(int i = n - 1, f = 0, g = n - 1; i >= 0; i--){
            
            if(f <= 0){
                f = 0;
                g = i;
            }
            f += q[i];
            if(f >= res){
                res = f;
                l = i;
                r = g;
            }
        }
        
        printf("%d %d %d\n", res, l, r);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38