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

动态规划：
dp[i]代表以arr[i]结尾的若干个子数组中的和的最大值。
状态转移方程：
dp[i] = arr[i], if dp[i -1] < 0
dp[i] = dp[i - 1] + arr[i], if dp[i - 1] >= 0
然后取dp数组里的最大值就行。

class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        int len = arr.size();
        int dp[len];  //以arr[i]结尾的子数组中的和的最大值；
        dp[0] = arr[0];
        int max = dp[0];
        for(int i = 1; i < len; i++)
        {
            if(dp[i - 1] < 0) dp[i] = arr[i];
            else dp[i] = arr[i] + dp[i - 1];
            if(dp[i] > max) max = dp[i];
        }
        return max;
    }
};