tech-interview-handbook
tech-interview-handbook copied to clipboard
Published
20 hours ago •
yangshun
yangshun
Change difficulty of "Maximum Subarray"
Difficulty of the "Maximum Subarray" question on LeetCode has been updated to medium.
I agree, I wondered if I'm stupid enough while attempting to solve it. Needs Kadane's algorithm.
The top-voted solution on Leetcode really made sense for me. I could not grasp this question for a long time too. Think of it as a DP algorithm rather than some fancy greedy algorithm: the subproblem is the maximum sum of a subarray ending at some index i, so dp(i) = max(dp(i-1) + A[i], A[i]). Basically, if the previous sum is negative, you are better off just starting a "new" subarray. The max sum would be the max of all dp(i) for i from 0 to n - 1 (inclusive). But, this question is no way "easy" by any means.
