Maximum Subarray (LeetCode 53): carry it or drop it, animated

Maximum Subarray is LeetCode problem 53, on four of the five big public interview lists. This video explains it from scratch with our own example, a food cart's eight daily profits where the best stretch of days (11) does not even contain the best single day (7): why trying every start and end is about five billion runs at a hundred thousand days, the one question that makes a single pass enough (what is the best run that ends exactly today?), the carry-or-drop rule (a negative run is dead weight, a positive run is a head start), and the real Python code running step by step. Every bar, carried amount and number on screen is read from the real run of the tested solution. Plus the classic trap (seeding best with zero instead of the first number returns zero for a list of losses) and the follow-ups interviewers ask: the days themselves, divide and conquer, and the biggest product. Problem: LeetCode 53, Maximum Subarray (Medium) · https://leetcode.com/problems/maximum... Pattern: Greedy · On: NeetCode 150, Blind 75, Grind 169, LeetCode Top Interview 150 Chapters 0:00 Cold open 0:17 The problem 0:43 The obvious answer 1:09 The trick 2:00 Dry run 3:27 The code 4:00 Cost and the trap 4:49 Follow-ups 5:16 The pattern The Python solution from the video def maximum_subarray(nums): best = nums[0] run = 0 for x in nums: run = max(run, 0) + x # a losing streak only drags us down best = max(best, run) return best Cost: O(n) time, O(1) extra memory. Sources • LeetCode 53: Maximum Subarray: https://leetcode.com/problems/maximum... • NeetCode 150: https://neetcode.io/problems/maximum-... • Blind 75: https://neetcode.io/practice • Grind 169 (community solutions list): https://github.com/open-minded13/leet... • LeetCode Top Interview 150: https://leetcode.com/studyplan/top-in... • Maximum subarray problem (history): https://en.wikipedia.org/wiki/Maximum... • CodePath guide: pitfalls (all-negative input): https://guides.codepath.org/compsci/M... The problem is explained in our own words with our own example. Every state in the animation comes from running the solution shown, and the code is tested (plus a random cross-check against the brute force) before the video is made. #LeetCode #MaximumSubarray #CodingInterview #DSA #Python