Leetcode 53. Maximum Subarray (Python)

Related Topic

Dynamic-Programming. Greedy.

Description

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

Sample I/O

Example 1

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

Methodology

This question solved by Dynamic Programming or greedy.

For dynamic programming:

1. Find the base case

   dp[0] = nums[0]
   

2. Find the pattern The basic idea is append the current value to the subarry of largest sum.
   1. If the subarray’sum greater than the current value, we keep the value in the subarry and make it become new subarray of largest sum.
   2. If the subarray’sum less than the current value, we abandon the former subarray of largest sum and create a new subarray of largest sum with head index value of current value.
3. To use dynamic programming for this question, we actually do not need continously create or abandon subarray. we can use prefix sum to always get the maxmium sum of previous subarry and compare the current value with this sum. This will lead to same result.

For greedy:

1. If all numbers are negative, then we return the largest negative number. Otherwise, there must be positive number.
2. We iterate the numbers, if the current sum + number is less than 0, then there is new subarray start, we will store the sum of the previous the subarray. Otherwise we will continue to append the number to the current subarray.

   Code

Dynamic Programming:

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

BigO

We iterate all dp array, it will cost O(n), each current value will compare with the sum of current value and last value, it will cost (1+1), in total will be O(n+n) and It is O(n)

Greedy:

def maxSubArray(self, nums: List[int]) -> int:
        if max(nums)<0:
            return max(nums)
        curr_sum, max_sum = 0, 0
        for num in nums:
            curr_sum = max(0, curr_sum + num)
            max_sum = max(curr_sum, max_sum)
        return max_sum

BigO

Time complexity : O(N) since it’s one pass along the array.