- 1、题目描述:
- 2、题目链接:
-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