Dynamic Programming in Maximum Subarray

Posted on | Edited on | In | Views:

Dynamic Programming in Maximum Subarray

When I did the problem in Leetcode, the problem of 53 is about the maximum subarray. I got in touch about the DP algorithm, which is very useful for solving this problem, converting the $O(n^3)$ to $O(n)$ complexity.

There are basically three approachs for this problem, the most time consuming one is the most straightforward and simple for user to come up with. Better one is the DP algorithm, which we are going to talk about.

Problem description:

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

Example:

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

Answer:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        DP algorithm
        '''
        n = len(nums)
        dp = [0]*(n)
        dp[0] = nums[0]
        for i in range(1,n):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

See the video for more details:

Reference:

  1. Lecture from Youtube.