Maximum Subarray

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Explanation
  3. 3. Code

Question

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

Explanation

Assume the local maximum is the maximum value of the continuous subarray which must contain the current value pointed by the index i. The function of local maximum can be expressed as localMax[i] = max(nums[i], localMax[i-1]+nums[i]). This can be explained by the examples below:

  1. if localMax[i-1]>0, nums[i]>0 then localMax[i] = localMax[i-1]+nums[i]
  2. if localMax[i-1]>0, nums[i]<0 then localMax[i] = localMax[i-1]+nums[i]
  3. if localMax[i-1]<0, nums[i]>0 then localMax[i] = nums[i]
  4. if localMax[i-1]<0, nums[i]<0 then localMax[i] = nums[i]

We also need a globalMax to store the global maximum value. In this case, although we take localMax[i-1]+nums[i] as local maximum which is smaller than localMax[i-1] when localMax[i-1]>0, nums[i]<0, we are still able to keep the localMax[i-1] with the existence of globalMax. With these two variables, we can get maximum of subarray with O(n) time complexity and O(1) space complexity.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        Two methods here, just select one.
        """
        # Time complexity O(n); Space complexity O(n)
        local = [nums[0]]
        globalMax = nums[0]
        for i in range(1,len(nums)):
            if local[-1] > 0:
                local.append(local[-1]+nums[i])
            else:
                local.append(nums[i])
            globalMax = max(globalMax, local[-1])
        return globalMax

        # Time complexity O(n); Space complexity O(1)
        if len(nums) == 0:
            return None
        elif len(nums) == 1:
            return nums[0]
        localMax = nums[0]
        globalMax = nums[0]
        for x in nums[1:]:
            localMax = max(x, localMax+x)
            globalMax = max(localMax, globalMax)
        return globalMax
Comments