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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        int sz = array.size();
        if(sz==1) return array;
        vector<int> dp(sz+1, 0);  //用于动态规划，存储之前的值
        int tmp = array[0];  //用来暂存最大和
        int lb=0, rb=0;      //左边界和右边界
        for(int i=1; i<=sz; ++i){
//             dp[i] = max(array[i-1], array[i-1]+dp[i-1]);  //用来存储右边界为i-1的最大和
            if(array[i-1] > array[i-1]+dp[i-1]){
                lb = i-1;
                dp[i] = array[i-1];
                cout << "lb: " << lb << "  dp[" << i << "]: " << dp[i];
            }
            else{
                dp[i] = array[i-1]+dp[i-1];
                cout << "lb: " << lb << "  dp[" << i << "]: " << dp[i];
            }
            if(dp[i]>=tmp){
                rb = i;
                tmp = dp[i];
                cout << "  rb: " << rb;
            }
//             tmp = max(tmp, dp[i]);
            cout << endl;
        }
        vector<int> ret;
        if(lb>rb){
            cout << "lb>rb  "<< endl;
            ret.push_back(array[rb-1]);
        }
        else
            for(int i=lb; i<rb; ++i){
                ret.push_back(array[i]);
            }
        return ret;
        
        /*
        int sz=array.size();
        vector<int> dp(sz+1, 1);
        dp[0] = 0;
        int ret = array[0];
        for(int i=1; i<=sz; ++i){
            dp[i] = max(array[i-1], dp[i-1]+array[i-1]);
            ret = max(ret, dp[i]);
        }
        return ret;
        */
    }
};