题解 | #最大连续子序列#

#include <algorithm>
#include<iostream>
#include <vector>
using namespace std;
int main()
{
    int n; 
    int maxv=0;
    while(cin>>n&&n)
    {
        vector<int> nums(n,0);//这个定义应该在输入n以后
        for(int i=0;i<n;i++)
        {
            cin>>nums[i];
        }
        int st=0,ed=0;
        int t_st=0,t_ed=0;//暂存开始和结束的坐标
        vector<int> dp(n,*min_element(nums.begin(), nums.end()));//dp[i]代表以i结尾的序列的最大连续子序列之和
        dp[0]=nums[0];
        maxv=*min_element(nums.begin(), nums.end());//最大连续子序列之和，初始化为最小值
        for(int i=1;i<n;i++)
        {/*dp[0]一定是nums[0],所以从第二个开始遍历：
        1.如果当前元素nums[i]加上之前的以i-1结尾的
        最大连续子序列之和dp[i-1]比当前元素nums[i]
        大----->那么，我们要寻找的最大连续子序列的
        开始坐标不用变，但是结束坐标需要暂时改变*/
            if(dp[i-1]+nums[i]>=nums[i])
            {
                t_ed=i;//结束坐标需要暂时改变
                dp[i]=dp[i-1]+nums[i];
                if(dp[i-1]+nums[i]>maxv)
                {//如果这次的连续子序列之和比之前统计的大，那么开始和结束的坐标需要改变
                    maxv=dp[i-1]+nums[i];
                    ed=t_ed;
                    st=t_st;
                }        
            }
            else 
            {
                dp[i]=nums[i];
                t_st=t_ed=i;
                if(nums[i]>maxv)
                {
                    maxv=nums[i];
                    st=t_st;
                    ed=t_ed;
                }
            }
        }
        /*若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素：
             maxv<0和全是负数的情况是互为充要条件，因为max<0,说明任何单独的
             元素都是小于0的，只要有一个不小于0，maxv都不可能小于0*/
        if(maxv<0) 
        {
            cout<<"0"<<" "<<nums[0]<<" "<<nums[nums.size()-1]<<endl;
        }
        else 
        {
            cout<<maxv<<" "<<nums[st]<<" "<<nums[ed]<<endl;
        }
    }
}