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 $\max_{0 \leq i < n} f[i]$.

Consider $f[i]$, where $i \geq 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 $\max_{0 \leq i < n} 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.

  • 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