PAT甲级1007 Max Subsequence Sum 子序列和最大问题

矫情吗；* 2023-05-31 02:34 12阅读 0赞

##### 解题思路： #####

1.将输入的数字存入数组，然后从第一个开始循环判断到最后一个  
2.**sum**累加当前数，如果值大于**max**，更新**rightindex**、**leftright**和**max**，用来记录队尾，但是如果**sum**值小于**0**，表示到目前位置的序列无效，因为负数只会拖累后面的出现的正数  
3.设置一个中间变量**tempindex**，用来指向新序列列头 规则是如果当前**sum**是**0**，指向下一个相邻的数  
4.题中还要求如果全是负数，输出**sum**为**0**，并输出第一个和最后一个数，可以设置**max**初值为 **-1**，在最后如果**max**还是 **-1** 表示**sum**从未有过大于 **-1**的情况，意味着全是负数，按规则输出数即可

#include<iostream>
    using namespace std;
    int main()
    { 
        int k,sum=0,max=-1,rightindex,leftindex,tempindex;//tempindex记录新的有效的队头
        cin>>k;
        int num[10005]={ 0};
        for(int i=0;i<k;i++)
        { 
            cin>>num[i];
        }
        for(int i=0;i<k;i++)
        { 
            sum+=num[i];
            if(sum<0)//之前计算的值全都无效
            { 
                tempindex=i+1;
                sum=0;
            }
            else if(sum>max)
            { 
                leftindex=tempindex;
                rightindex=i;
                max=sum;
            }
        }
        if(max==-1)cout<<0<<" "<<num[0]<<" "<<num[k-1];//全是负数的情况
        else 
        { 
            cout<<max<<" "<<num[leftindex]<<" "<<num[rightindex];
        }
        return 0;
    }