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

动态规划：

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        if (arr.size() == 0) return 0;
        vector<int> dp(arr.size(), 0);
        int maxsum = arr[0];
        dp[0] = arr[0];   // dp[i] 表示从arr[0]~arr[i]的最大累加和
        for (int i = 1; i < arr.size(); ++i) {
            dp[i] = max(arr[i], dp[i-1] + arr[i]);  // 递推公式
            maxsum = max(maxsum, dp[i]);
        }
        return maxsum;
    }
};