LeetCode 53. Maximum Subarray — Python Solution
Blind 75 — Programming & Technical Interview Questions — Explanation Series
Published in
3 min readJun 21, 2022
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…