acwing每日一题-9

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 1 分钟
acwing每日一题-最大连续子序列

题目

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

最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 {−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 组数据。

输入样例：

1
2
3
4
5
6
7
8
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
27 0 7
10 0 0
3 3 3
0 0 0

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        long long nums[100010],sum[100010],l=0,r=0,ans=-1,m=0;
        for(int i=0;i<n;i++)
        {
            cin >> nums[i];
            sum[i]=max(sum[i-1]+nums[i],nums[i]);
            if(sum[i-1]<0) m=i;
            if(sum[i]>ans) ans=sum[i],l=m,r=i;
        }
        if(ans<0) cout<<"0 0 0"<<endl;
        else cout<<ans<<" "<<l<<" "<<r<<endl;
    }
    return 0;
}