题解 | #连续子数组的最大和(二)#

public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        vector<int> dp(array.size(),0);
        int mymax=INT_MIN;
        for(int i=0;i<array.size();i++){
            if(i==0){
                dp[i]=array[i];
            }
            else{
                dp[i]=max(array[i],dp[i-1]+array[i]);
            }
            mymax=max(mymax,dp[i]);
        }
        int flag=-1;
        int length=0;
        for(int i=array.size()-1;i>-1;i--){
            if(dp[i]==mymax){
                int j=i;
                int templength=1;
                while(j!=0&&dp[j-1]+array[j]==dp[j]){
                    templength++;
                    cout<<"templength="<<templength<<"j="<<j<<endl;
                    j--;
                    cout<<dp[j-1]<<array[i]<<dp[j]<<endl;
                }
                if(templength>length){
                    flag=i;
                    length=templength;
                }
            }
        }
        vector<int> resu(array.begin()+flag-length+1,array.begin()+flag+1);
        return resu;
    }
};