Blind 75.05 - Maximum Subarray
Maximum subarray.
Problem descriptionPermalink
Given an integer array nums
, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <=
105- −104
<= nums[i] <=
104
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.
Solution typePermalink
Dynamic programming (caching). You could categorize this as a sliding window solution as well, although the window size is variable here.
SolutionPermalink
I didn’t get this one within the hour (first one in this series!), which I’m pretty annoyed about because it’s “just” an array problem. I feel a little less bad reviewing the solutions though, because the best algorithm has someone’s name attached to it!
This problem is only interesting with negative numbers included in the array; otherwise the entire array is the max subarray. The first thing that comes to mind is “how do I determine whether a given range of elements is positive or negative?”. That leads into a divide-and-conquer approach I tried later; the first thing I tried was to find the left and right borders of the subarray in a sort of array prefix / suffix approach:
def maxSubArray(self, nums: List[int]) -> int:
maxSum = sum(nums)
left = 0, right = len(nums)
s = sum(nums)
for i in range(len(nums) - 1, 0, -1):
s -= nums[i]
if s > maxSum:
maxSum = s
right = i
s = sum(nums)
for i in range(len(nums), right):
s -= nums[i]
if s > maxSum:
maxSum = s
left = i
return sum(nums[left:right])
The problem with this algorithm is that when you do the first pass to calculate right
, it assumes the position of left
. (Note left
is inclusive, right
is exclusive.) I thought this was fine because I was thinking “if it’s the optimal boundary when considering the whole array, then it will be the optimal boundary for the optimal subarray as well”. However, this misses cases like [-100, -100, 1, -100, -100]
where if you assume left
is fixed at index 0, then right
should go to index 1 instead of index 3.
Since LeetCode gave a hint to try divide and conquer, I tried divide and conquer. Here, the idea was to combine subarrays by seeing which is best: the optimal subarray in the left, the optimal subarray in the right, or the subarray formed by the leftmost and rightmost indices from both arrays.
def maxSubArrayHelper(self, nums: List[int]) -> List[int]:
if len(nums) == 0:
return [0, 0]
if len(nums) == 1:
return [0, 1]
leftIdxs = self.maxSubArrayHelper(nums[0 : len(nums) // 2])
rightIdxs = self.maxSubArrayHelper(nums[len(nums) // 2 : len(nums)])
# there's a functional way to do this but idr lol
for i in range(2):
rightIdxs[i] += len(nums) // 2
# three options:
# just the left
# just the right
# combine both going through the middle
leftSum = sum(nums[leftIdxs[0] : leftIdxs[1]])
rightSum = sum(nums[rightIdxs[0] : rightIdxs[1]])
combinedSum = sum(nums[leftIdxs[0] : rightIdxs[1]])
maxSum = max(leftSum, max(rightSum, combinedSum))
if leftSum == maxSum:
return leftIdxs
if rightSum == maxSum:
return rightIdxs
return [leftIdxs[0], rightIdxs[1]]
def maxSubArray(self, nums: List[int]) -> int:
bestIdxs = self.maxSubArrayHelper(nums)
print(bestIdxs)
return sum(nums[bestIdxs[0] : bestIdxs[1]])
Here, the problem is in the third case. The optimal subarray might use an index in between the indices you’ve already calculated. For example, in the first example test case given ([-2,1,-3,4,-1,2,1,-5,4]
), we return the sum of the subarray with indices [3,9]
instead of [3,7]
. [8,9]
is optimal for the subarrays [...,-5,4]
and [...,-1,2,1,-5,4]
, and the algorithm never recalculates that the right index should be 7 instead of 9 when combining into the whole array. In other words, this algorithm doesn’t correctly take local optimality and turn it into global optimality.
I identified the brute force solution quickly, but I don’t think I spent enough time asking “where is the inefficiency in the brute force solution?” and I was too attracted to an idea similar to 75.04 (product except self) where you’d go from the start / end of an array and use prefix / suffix accumulator variables to figure out what to include or cut. I also didn’t spend enough time thinking about the edge cases. The optimal solution doesn’t need to think about them,
In an actual interview, I’d want to outline the brute force solution first and foremost to demonstrate my thinking, then try out ideas. Honestly, that’s something I should do regularly for these problems: write a brute force solution, paste it here, then optimize. I’ll try to do that going forward…
The actual solution is fundamentally based on caching, although most articles will call it dynamic programming instead (perfectly valid).
def maxSubArray(self, nums: List[int]) -> int:
bestSum, currentSum = nums[0], 0
for elt in nums:
currentSum = max(elt, currentSum + elt)
bestSum = max(bestSum, currentSum)
return bestSum
One thing I’ll point out about the solution is that it doesn’t juggle index variables at all; it just tracks the sum. The fact that the problem returns a sum is kind of a hint at that; I knew I was being unoptimal with my solutions because I had a bunch of index variables.
The big concept that I missed was that we have to answer the question “Should we start a new counter at this index or no?”. The accumulator variable is similar to the idea I had with suffixes and prefixes, but I did not have the correct idea when thinking about “when do we actually start our subarray?”. There’s a few other solutions that use DP and divide and conquer (you can find them on leetcode if you want), but I think this is the important central idea: using a pseudo-sliding window of variable length.
This is called Kadane’s algorithm, and if Kadane thought it was cool enough to put his name on it then I don’t feel so bad not coming up with it myself! Very well, on to the next.
Leave a comment
Your email address will not be published. Required fields are marked. *