LeetCode 53. Maximum Subarray — Python Solution

Blind 75 — Programming & Technical Interview Questions — Explanation Series

The problem:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Note: A subarray is a contiguous part of an array.

The constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

The examples:

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

The explanation:

This is a dynamic programming problem, even with that in mind it is easy to get tripped up on this problem. As with most DP problems, you create an array to keep track of values you calculate. For this problem, that would be the sums of the subarrays. Of course there is the brute force solution, O(n²), where you use a nested for-loop and calculate every single sum…