Change difficulty of "Maximum Subarray"
Shri333 opened this issue · 3 comments
Shri333 commented
Difficulty of the "Maximum Subarray" question on LeetCode has been updated to medium.
Hesham-Salama commented
I agree, I wondered if I'm stupid enough while attempting to solve it. Needs Kadane's algorithm.
Shri333 commented
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.