[LeetCode] Challenge log 53

Posted on |
53. Maximium Subarray

https://leetcode.com/problems/maximum-subarray/description/

It is mainly a DP problem.

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution:

DP thought:

  • last represents the largest sum in the subarray that ends with current pointer.
  • The key is last[p] = max(last[p-1], 0) + nums[p], meaning we only include last[p-1] if it is positive
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = last = nums[0]
        p = 1
        while p<len(nums): 
            last = nums[p] + max(last, 0)
            result = max(result, last)
            p += 1
        return result
0%