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、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-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就需要更新
        }
        return res;
    }
};

Java版本：

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

Python版本:

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        dp = [0] * (len(array) +10)#dp[i]代表在下标为i时子数组的值
        dp[0] = array[0]#dp[0]就应该等于array的第一个元素
        res = array[0]#用来保存子数组的最大值
        for i in range(1,len(array)):
            #因为是连续，所以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就需要更新
        return res