秋招每日一题T28——最大连续子序列

题目描述

给定 K 个整数的序列 {N0,N1,…,NK−1}，其任意连续子序列可表示为 {Ni,Ni+1,…,Nj}，其中 0≤i≤j

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

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

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

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

第 2 行给出 K 个整数 N1,…,NK。

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

所有元素下标为 0∼K−1。

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

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

数据范围
1≤K≤105,
−10000≤Ni≤10000,
输入最多包含 10 组数据。

思路

〇本题来自中南大学的考研机试题。
①题目是裸的DP模板题，但是要同时输出最大连续子序列的左右边界，这个确实卡了一会儿。
②当前的f[i]为局部最优时，更新总和res和左右边界l和r即可，仍是dp的思路。

代码

#include 
#include 
#include 
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn] = {0},f[maxn] = {0};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		int l=1,r=1;
		int sum = a[1];
		for(int i=1,j=1;i<=n;i++){
			f[i] = max(f[i-1],0) + a[i];
			if(f[i-1] < 0){
				j = i;
			}
			if(f[i] > sum){
				sum = f[i];
				l = j,r = i;
			}
		}
		if(sum < 0){
			cout<<"0 0 0"<<endl;
		}
		else{
			cout<<sum<<' '<<l-1<<' '<<r-1<<endl;
		}
	}	
	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