PAT_1007 Maximum Subsequence Sum

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

解析：类似最大子段和问题，由于要输出和的同时，还要输出子段的第一位、最后一位，所以在处理的时候记录一下每个以a[i]结束的子段的最大字段和、该子段的首位置。

策略：如果tmp小于0，就取a[i]为首部（需要更改tmpplace子段首位置），否则将tmp接上a[i]

特判：如果所有数都小于0，输出0+第一个数+最后一个数，注意输出的是数不是位置！

如果这题理解不了可以暂时跳过~建议倒序刷题

#include<bits/stdc++.h>
using namespace std;
int a[10050]={0},q[10050]={0},f[10050]={0};
int main()
{
    int n,res=0,tmp=0,tmpplace=0;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    
    //假设第一个数必取
    tmp=res=q[0]=a[0];
    for(int i=1;i<n;i++)
    {
        if(tmp<0)tmp=a[i],tmpplace=i;
        else tmp+=a[i];

        res=max(res,tmp);
        //q[i]表示必取i、往前延伸的最大字段和，tmpplace表示延伸到哪一位
        q[i]=res;
        f[i]=tmpplace;
    }
    //检查是否所有数为负
    if(res<0)
    {
        cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        if(q[i]==res)
        {
            cout<<res<<" "<<a[f[i]]<<" "<<a[i]<<endl;
            return 0;
        }
    }
    return 0;
}