NC67连续子数组的最大和

NC67连续子数组的最大和

- 1、题目描述：

- 2、题目链接：

https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=190&tqId=35198&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
-3、 设计思想：

详细操作流程看下图：

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

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        vector<int>dp(array.size() +10,0);//dp[i]代表在下标为i时子数组的值
        dp[0] = array[0];//dp[0]就应该等于array的第一个元素
        int res = array[0];//用来保存子数组的最大值
        for(int i = 1;i < array.size();i ++){
            //因为是连续，所以i-1位置时的子数组值如果小于0，就没必要在加了，因为越加越小
            //如果大于0就让，dp[i] = dp[i-1] + array[i]
            dp[i] = max(dp[i-1],0)+array[i];
            res = max(res,dp[i]);//dp只要更新，res就需要更新
        }