Leetcode: Maximum Subarray

Maximum Subarray


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.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/maximum-subarray
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
## Basic Ideas: Dynamic programming
##              Get sums[i]: it's the sum from nums[0] to nums[i]
##
##              f(n) = max(f(n-1), sums[n], sums[n] - min(sums))
##
## Complexity: Time O(n), Space (n)
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        sums = [0] * length
        sum_v = 0
        for i in range(0, length):
            sum_v += nums[i]
            sums[i] = sum_v

        # start from the very beginning
        min_sum = 0
        max_list = [0]*length
        # the first element
        max_list[0] = sums[0]
        for i in range(0, length-1):
            min_sum = min(min_sum, sums[i])
            max_list[i+1] = max(max_list[i], sums[i+1], sums[i+1]-min_sum)
        return max_list[-1]

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.