01-复杂度2 Maximum Subsequence Sum-CSDN博客

本文链接：https://blog.csdn.net/peterchen96/article/details/79972949

本文介绍了一种求解最大子序列和问题的方法，并通过一个示例程序详细展示了如何找到给定整数序列中具有最大和的连续子序列及其边界元素。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：中国大学MOOC-陈越、何钦铭-数据结构-2018春
作者: DS课程组
单位: 浙江大学

问题描述：
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

解答：计算最大子列和用在线处理即可，这道题还要输出子列首末位置的数，我采用记录目前确认的最大子列和的尾位置和子列和的长度来做。当遇到现有子列和大于最大子列和时更新尾位置的信息和子列长度信息，当现有子列和小于0，即前一段子列和要被放弃时，把长度信息归零为计算下一段子列和做准备。
注意全部负数的判断，我用了一个标记来检验是否全负，并在最后输出阶段进行判断。

#include <iostream>
using namespace std;

const int maxn=10000;
int input[maxn];
int savePos[2];
int main()
{
    int N;
    cin>>N;
    bool isAllNegtive=true;
    int maxSum=-1,tempSum=0,endPos,len=0,maxlen=0;
    for(int i=0; i<N; i++)
    {
        cin>>input[i];
        tempSum+=input[i];
        len++;
        if(tempSum>maxSum)
        {
            maxSum=tempSum;
            endPos=i;
            maxlen=len;
            isAllNegtive=false;
        }
        if(tempSum<0)
        {
            tempSum=0;
            len=0;
        }
    }
    if(isAllNegtive)
        cout<<"0 "<<input[0]<<" "<<input[N-1];
    else
        cout<<maxSum<<" "<<input[endPos-maxlen+1]<<" "<<input[endPos];
    return 0;
}