DSA · Dynamic programming (Kadane) · #23
Maximum Subarray
Module 26 · difficulty 2/5·⏱ 30:00starts on first keystroke
Given an integer array `nums`, find the contiguous subarray (containing at least one number) with the largest sum and return that sum.
Examples
nums = [-2,1,-3,4,-1,2,1,-5,4]→6— subarray [4,-1,2,1]nums = [1]→1nums = [5,4,-1,7,8]→23
Stuck? Reveal an animated walkthrough of the approach.
Constraints
- · 1 <= nums.length <= 10^5
- · -10^4 <= nums[i] <= 10^4
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.