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

#include <vector>
class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        vector<int> dp(array.size(), 0);
        int l = 0, r = 0;
        int res1 = 0, res2 = 0, res3 = 0, res4 = 0;
        dp[0] = array[0];	//动态规划，保存已操作过的结果
        int max_val = array[0];
        int max_val_1 = array[0];
        for(int i = 1; i < array.size(); ++i)
        {
            r++;
            dp[i] = max(dp[i-1] + array[i], array[i]);
            // 更新l值
            if(dp[i-1] + array[i] < array[i]){
                l = r;  // 这不能给i，因为r一开始为0，而i一开始为1
                // std::cout << " 888 " << std::endl;
            }

            // int tmp = max_val_1;
            // max_val_1 = max(dp[i], max_val_1);
            // // 序列更新,最大值更新或者更长了~
            // if(max_val_1 > tmp || (max_val_1 == tmp && (r - l +1)> (res4 -res3+1))){
            //     res3 = l;
            //     res4 = r;
            //     std::cout <<i <<" max_val_1 : " << " " << dp[i]<< " "<< l << " " << r << " " << max_val << std::endl;
            // }    // 这种写法会报错，逻辑上个人理解没毛病，但从打印效果看最大值更新会更频繁
            // 序列更新：最大值更新，或者相等情况下，题意更长则更优
            if(dp[i] > max_val || max_val == dp[i] && (r - l +1)> (res2 -res1+1)){
                max_val = dp[i];
                res1 = l;
                res2 = r;
                // std::cout <<i <<" max_val__ : " <<  " " << dp[i]<< " "<< l << " " << r << " " << max_val << std::endl;
            }
        }
        vector<int> v;
        v.assign(array.begin()+res1, array.begin()+res2+1);
        return v;
    }
};