Leet Code 53. Maximum Subarray— Detailed Explained Python3 Solution
Problem 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:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.Solution
Obvious Solution
The obvious (and brute force) way is list all contiguous subarray and then calculate each one’s sum to get the largest one out.
For subarrays starting from 1st number, there will be N subarrays; forsubarrays starting from 2nd number, N-1 subarrays; … So in total, I need to calculate N+N-1+N-2+…+1 which is O(N²) without taking the calculation of the sums of subarrays.
Obviously, obvious solution is too time consuming.
Best Solution (to me)
The intuition is the quickest one should be O(N). The reason is at least I need to visit each element once. Let me imaging when I run into a number with index = x, the largest sum of a subarray ending with x should be a largest sum of “prefix” subarray ending with x-1 plus the number at x. It can be a little hard to understand so let me use an example: assuming in [-2,1,-3,4,-1,2,1, -5,4], now I’m looking to find a subarray that ends with index=2 (number is -3) and having the largest sum.
There will be 2 “prefix” candidates: [-2,1], [1], they can join with -3 to make 2 candidates [-2,1,-3] and [1,-3]; also, there is possible neglectable point, I can use NONE of “prefix” and just use current number to make a subarray, so there is another candidate which is [-3]. Out of [-2,1,-3], [1,-3], [-3], who will be the one with largest sum? It will be [1,-3] while the prefix is [1] which has the largest sum of all subarrays ending with index=1 (nubmer is 1).
So this is actually a dynamic programming problem. If dp[i] represents the largest sum of all subarrays ending with index i, then its value should be the larger one between nums[i] (without using prefix) and dp[i-1] + nums[i] (using prefix with largest sum plus current number):
dp[i] = max(dp[i-1] + nums[i], nums[i])
# to start with, dp[0] = nums[0]So I just need to calculate dp[0], dp[1]…, dp[n] while comparing each one with current largest sum, if dp[i] > current_largest_sum then current_largest_sum = dp[i].
Time & Space Complexity
For time complexity, the best solution is O(N) since it only visits each element of input array for once.
Space complexity is also O(N) since there is an auxiliary array (dp) is used. This can be optimized since essentially, when calculating dp[i], I only need dp[i-1] and not the rest (like dp[i-2], dp[i-3]…). So I can reduce space complexity to O(1) by dropping the array (dp) and just use a variable to keep last value (which is dp[i-1]).
Extended Reading
Python3 cheatsheet:
https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549
