题解 | # 子数组的最大累加和问题 #

思路

1、动态规划

2、dp[i] = dp[i-1]+arr[i]或者dp[i] = arr[i]

代码

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector& arr) {
        // write code here
        // 动态规划
        vector dp(arr.size()+1, INT_MIN);        // 代表当前位置及其之前的最大和
        dp[0] = arr[0];
        int max_num = dp[0];
//         dp[1] = max(dp[0]+arr[1], dp[0])
        for(int i = 1; i<arr.size(); i++){
//             if(dp[i-1]>0){            // 前面的大于0,
//                 dp[i] = dp[i-1]+arr[i];
//             }
//             else                        // 前面的小于0，直接算本身
//                 dp[i] = arr[i];
            dp[i] = max(dp[i-1]+arr[i], arr[i]);

            max_num = max(max_num, dp[i]);
        }

        return max_num;
    }
};