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

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
       //简单好理解
        int inf=-0x3f3f3f3f,maxn=-0x3f3f3f3f;//无穷小
        int sum=0,newletf=0,newright=0,letf=0,right=0;
        vector<int>ret;
        for(int i=0;i<array.size();i++){//这里可以用动态规划找出最大值
            sum=max(sum+array[i],array[i]);
            inf=max(inf,sum);//记录最大值
        }
        sum=0;
        //用newletf和newright两个指针枚举最大长度（已知最大值）
        for(int i=0;i<array.size();i++){
            if(sum+array[i]>=array[i]){
                sum=sum+array[i];
            }
            else{
                sum=array[i];
                newletf=newright;
            }
            //找出最大值的最大长度，找到就更新长度letf和right
            if(sum==inf&&newright-newletf>=right-letf){
                    letf=newletf;
                    right=newright;
                    
                }
                    newright++;//指针后移，继续往后找
        }
//        cout<<letf<<" "<<right<<" ";
        for(int i=letf;i<=right;i++){//根据最大长度赋值ret
            ret.push_back(array[i]);
        }
        return ret;
    }
};