动态规划——NC19. 子数组的最大累加和问题

题目：

思路：

1. dp数组的定义：dp[m] 代表在arr[m]时的最大子数组和
2. base_case：
3. 状态转移方程：化简了，思路就是要么加入之前的，要么另起炉灶。

代码：

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int sz = arr.size();
        int maxsum = arr[0];
        for(int i = 1; i < sz; i ++) {
            arr[i] = max(arr[i], arr[i]+arr[i-1]);
            maxsum = max(arr[i], maxsum);
        }
        return maxsum;
    }
};

Rank：

就不贴了，就一般偏下水平，牛客是真的绝。

Tips：