子数组的最大累加和（动态规划）

/*
dp[i]:以i为结尾的数组最大和 
dp[i]:初始化为a[i].
dp[i] = max(dp[i], dp[i-1] + a[i]);
结果为遍历所有dp，寻找以i为结尾的最大值
*/
class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        vector<int> dp(arr);
        for(int i = 0;i < arr.size(); i++){
            dp[i] = max(dp[i], dp[i-1] + arr[i]);
        }
        int ans = 0;
        for(int i = 0;i < arr.size(); i++){
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};