1007. Maximum Subsequence Sum (25)

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

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

Sample Output:

10 1 4

思路:题意是求序列中最大子序列和,并要标记第一个最大子序列的开始元素和结束元素,遍历序列,若当前子序列和大于最大值,就更新开始元素和结束元素和最大值,若当前子序列小于零就将子序列和置零并将记录临时开始元素为下一个,算法复杂度为O(n)。

Code:

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,arr[10010];    
    cin>>n;
    int flag=0,st=1,ed=n,max=-1,sum=0,tpst=1;
    for(i=1;i<=n;++i)
    {
        cin>>arr[i];
        if(arr[i]>=0)
            flag=1;
    }
    if(flag==0)
        cout<<0<<" "<<arr[st]<<" "<<arr[ed]<<endl;
    else
    {
        for(i=1;i<=n;++i)
        {
            sum+=arr[i];
            if(sum>max)
            {
                max=sum;
                st=tpst;
                ed=i;
            }
            if(sum<0)
            {
                sum=0;
                tpst=i+1;
            }            
        }
        cout<<max<<" "<<arr[st]<<" "<<arr[ed]<<endl;
    }
    return 0;
}

打个小广告

欢迎加入我的知识星球「基你太美」,我会在星球中分享 AucFrame 框架、大厂面经、AndroidUtilCode 更详尽的说明…一切我所了解的知识,你可以通过支付进入我的星球「基你太美」进行体验,加入后优先观看星球中精华的部分,如果觉得星球的内容对自身没有收益,你可以自行申请退款退出星球,也没必要加我好友;如果你已确定要留在我的星球,可以通过扫描如下二维码(备注:基你太美+你的星球昵称)加我个人微信,方便我后续拉你进群(PS:进得越早价格越便宜)。

我的二维码