NC19子数组的最大累加和问题

NC19子数组的最大累加和问题

- 1、题目描述：

- 2、题目链接：

https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=117&&tqId=35068
-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

 class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        //dp[i]代表到第i位的时侯,以arr[i]结尾的连续子数组最大累加和
        int dp[arr.size()];//开辟dp
        dp[0] = arr[0];//初始化
        int res = arr[0];//保存最终的结果
        for(int i = 1;i < arr.size();i ++){
            dp[i] = max(0,dp[i-1]) + arr[i];//维护dp[i]
            res = max(res,dp[i]);//每更新一个dp值就更新一下res
        }
        return res;
    }
};

Java版本：

impo