Maximum Subsequence Sum（c++）

PTA数据结构
提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 题目
• • **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.
• 一、输入输出样例
• 二、实现代码

---

题目

提示：这里可以添加本文要记录的大概内容：

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 aximum 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.

提示：以下是本篇文章正文内容，下面案例可供参考

一、输入输出样例

输入：
10
-10 1 2 3 4 -5 -23 3 7 -21
输出：
10 1 4

二、实现代码

代码如下（示例）：

#include 
using namespace std;
int main(){
    
    int numsize;
    int i=0;
    //scanf("%d",&numsize);
    cin>>numsize;
    int arr[numsize];
    for(;i<numsize;i++){
        //scanf("&d",&arr[i]);
        cin>>arr[i];
    }
    int max=arr[0];
    int thisnum=0;
    int tempStart=0,tempEnd=0,start=0,end=0;
    for(i=0;i<numsize;i++){
        
        if(thisnum>=0){
            thisnum+=arr[i];
            tempEnd=i;//巧妙运用了一个预存数
        }
        else if(thisnum<0){//舍弃掉前一个负数
            tempStart=i;
            tempEnd=i;
            thisnum=arr[i];
        }
        if(thisnum>max)
            {
                max=thisnum;
                start=tempStart;
                end=tempEnd;
            }
    }
    if(max<0){
        cout<<"0"<<" "<<arr[0]<<" "<<arr[numsize-1]<<endl;
    }
    else{
    cout<<max<<" "<<arr[start]<<" "<<arr[end]<<endl;
    }
    return 0;
}

---