53_Maximum Subarray-最大子数组

问题描述

Given an integer array nums, find the subarray with the largest sum, and return its sum.

给定一个数组nums， 找到一个子数组。使它的和最大，返回子数组

例子

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: 子数组 [4,-1,2,1] 有最大的和6.

基本思想

这是一个动态规划的问题。解题思路类比于最大递增序列。如下：

• 构建数组dp，其大小为nums的长度。其中dp[i] 表示 以 nums[i] 为结尾的子数组的最大的和
• 则dp[i]的大小取决于如下两个变量 dp[i-1]+nums[i] , nums[i]
  • 如果 dp[i-1]+nums[i] < nums[i], 则 dp[i] = dp[i-1]+nums[i] 表示nums[i]加入以nums[i-1]为结尾拥有最大和的子数组中
  • 如果 dp[i-1]+nums[i] >= nums[i], 则dp[i] = nums[i] 表示 以nums[i]结尾的最大和的子数组只有一个元素

时间复杂度 O(n),空间复杂度O(n)

代码

C++

   int maxSubArray(vector<int>& nums) {
      if (nums.size()<=0)  return 0;
      int size = nums.size();
      vector<int> dp(size, 0);
      dp[0] = nums[0];
      int maxSum = dp[0];
      for(int i=1;i<size;++i) {
        dp[i] = max(nums[i], nums[i]+dp[i-1]);
        maxSum = max(dp[i], maxSum);
      }
      return maxSum;
    }

python

    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)<=0: return 0
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1,len(nums)):
            dp[i] = max(nums[i], nums[i]+dp[i-1])
        return max(dp)