Fork me on GitHub

Max Sum SubArray & Max Product SubArray

Posted on

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.

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        yet_max = nums[0]
        lens = len(nums)
        ret = nums[0]
        for i in range(1, lens):
            yet_max = max(nums[i], nums[i] + yet_max)
            if yet_max > ret:
                ret = yet_max
        
        return ret

Extension

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

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

Example 2:

1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

In this context, we need to maitain two arrays to record the local max product and local min product which end with the char before the current one.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        yet_min = nums[0]
        yet_max = nums[0]
        ret = nums[0]
        lens = len(nums)
        
        for index in range(1, lens):
            raw_yet_max = yet_max
            yet_max = max(nums[index], nums[index]*yet_max, nums[index]*yet_min)
            yet_min = min(nums[index], nums[index]*raw_yet_max, nums[index]*yet_min)
            
            if yet_max > ret:
                ret = yet_max
            
        return ret