- 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