Welcome to Subscribe On Youtube

53. Maximum Subarray

Description

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

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solutions

Solution 1: Dynamic Programming

We define $f[i]$ to represent the maximum sum of the continuous subarray ending with the element $nums[i]$. Initially, $f[0]=nums[0]$. The final answer we are looking for is $\underset{0\le i<n}{max}f[i]$.

Consider $f[i]$, where $i\ge 1$, its state transition equation is:

$$f[i]=max\{f[i-1]+nums[i],nums[i]\}$$

Which is also:

$$f[i]=max\{f[i-1],0\}+nums[i]$$

Since $f[i]$ is only related to $f[i-1]$, we can use a single variable $f$ to maintain the current value of $f[i]$, and then perform state transition. The answer is $\underset{0\le i<n}{max}f$.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. We only need to traverse the array once to get the answer. The space complexity is $O(1)$, we only need constant space to store several variables.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• C#
• RenderScript

• class Solution {
      public int maxSubArray(int[] nums) {
          int ans = nums[0];
          for (int i = 1, f = nums[0]; i < nums.length; ++i) {
              f = Math.max(f, 0) + nums[i];
              ans = Math.max(ans, f);
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
          int ans = nums[0], f = nums[0];
          for (int i = 1; i < nums.size(); ++i) {
              f = max(f, 0) + nums[i];
              ans = max(ans, f);
          }
          return ans;
      }
  };
  

• class Solution:
      def maxSubArray(self, nums: List[int]) -> int:
          res = cur_sum = nums[0]
          for num in nums[1:]:
              cur_sum = num + max(cur_sum, 0)
              res = max(res, cur_sum)
          return res
  
  

• func maxSubArray(nums []int) int {
  	ans, f := nums[0], nums[0]
  	for _, x := range nums[1:] {
  		f = max(f, 0) + x
  		ans = max(ans, f)
  	}
  	return ans
  }
  

• function maxSubArray(nums: number[]): number {
      let [ans, f] = [nums[0], nums[0]];
      for (let i = 1; i < nums.length; ++i) {
          f = Math.max(f, 0) + nums[i];
          ans = Math.max(ans, f);
      }
      return ans;
  }
  
  

• /**
   * @param {number[]} nums
   * @return {number}
   */
  var maxSubArray = function (nums) {
      let [ans, f] = [nums[0], nums[0]];
      for (let i = 1; i < nums.length; ++i) {
          f = Math.max(f, 0) + nums[i];
          ans = Math.max(ans, f);
      }
      return ans;
  };
  
  

• public class Solution {
      public int MaxSubArray(int[] nums) {
          int ans = nums[0], f = nums[0];
          for (int i = 1; i < nums.Length; ++i) {
              f = Math.Max(f, 0) + nums[i];
              ans = Math.Max(ans, f);
          }
          return ans;
      }
  }
  

• impl Solution {
      pub fn max_sub_array(nums: Vec<i32>) -> i32 {
          let n = nums.len();
          let mut ans = nums[0];
          let mut f = nums[0];
          for i in 1..n {
              f = f.max(0) + nums[i];
              ans = ans.max(f);
          }
          ans
      }
  }
  
  

All Problems

All Solutions