Maximum subarray#

Levels: level-2

Data structures: array

Algorithms: divide-and-conquer, dynamic-programming

Practice Link#

LeetCode

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#

text

1Input: [-2,1,-3,4,-1,2,1,-5,4],
2Output: 6
3Explanation: [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.

Python Solution#

 1class Solution(object):
 2    def maxSubArray(self, nums):
 3        if not nums:
 4            return 0
 5        best_sum = nums[0]
 6        current_sum = 0
 7        for x in nums:
 8            current_sum = max(x, current_sum + x)
 9            best_sum = max(best_sum, current_sum)
10        return best_sum
11
12
13in_arrs = [
14    [2, 1, 2, 1, 0, 1, 2],
15    [3, 3, 5, 0, 0, 3, 1, 4],
16    [3, 5, 0, 1, 4],
17    [1, 2, -1, 1],
18    [1, 2, 3, 4],
19    [1, 1, 1, 3, 3, 4, 3, 2, 4, 2],
20    [-2, 1, -3, 4, -1, 2, 1, -5, 4],
21]
22if __name__ == "__main__":
23
24    sol = Solution()
25    for nin in in_arrs:
26        r = sol.maxSubArray(nin)
27        print(r)