menu

[LeetCode] 053. Maximum Subarray *

Problem (Easy)

053. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

  • Input: [-2,1,-3,4,-1,2,1,-5,4],
  • Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

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.

Approach 1: Brute Force (Time Limit Exceeded!)

Idea

Double loop, verify all possible subarray’s sum.

Solution

class Solution1:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = nums[0]
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                #print('i:', i, 'j:', j, 'sum:', sum(nums[i:j+1]))
                if sum(nums[i:j+1]) > s:
                    s = sum(nums[i:j+1])
        return s

Complexity

  • Time: $O(n^2)$
  • Space: $O(n)$

  • Approach 2: DP

Idea

DP solution & some thoughts

Solution

class Solution2:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [None for i in range(len(nums))]
        dp[0] = nums[0]

        for i in range(1, len(nums)):
            if dp[i-1] > 0:
                dp[i] = nums[i] + dp[i-1]
            else:
                dp[i] = nums[i]
        return max(dp)

Complexity

  • Time: $O(n)$
  • Space: $O(n)$



KF

Comments