Find the contiguous subarray with the largest sum (Kadane's algorithm).

How to think about it

Recognise the pattern

The signal is “maximum/minimum sum of a contiguous subarray”. Kadane’s algorithm is a classic example of a greedy-DP hybrid: at each position you make a locally optimal choice (“should I extend or restart?”), and the global optimum falls out naturally. Any time the words “contiguous” and “maximum sum” appear together, reach for Kadane’s.

Build the approach step by step

Brute force computes the sum of every (i, j) subarray: O(n²) or O(n³) depending on whether you reuse partial sums.

The key question at each element: is it better to extend the subarray ending at the previous element, or to throw it away and start a new subarray at the current element?

• If current_sum + nums[i] > nums[i], extending is better → current_sum += nums[i]
• Otherwise (current_sum was negative), starting fresh is better → current_sum = nums[i]

This simplifies to: current_sum = max(nums[i], current_sum + nums[i]).

After each update, check if current_sum > global_max.

Walk through [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

i=0: cur=max(-2,-2)=-2, best=-2
i=1: cur=max(1,-1)=1,   best=1
i=2: cur=max(-3,-2)=-2, best=1
i=3: cur=max(4,2)=4,    best=4
i=4: cur=max(-1,3)=3,   best=4
i=5: cur=max(2,5)=5,    best=5
i=6: cur=max(1,6)=6,    best=6
i=7: cur=max(-5,1)=1,   best=6
i=8: cur=max(4,5)=5,    best=6

Answer: 6 (subarray [4,-1,2,1])

Complexity

• Time — O(n): one forward pass, one decision per element.
• Space — O(1): two variables (current_sum and best).

The trap and a common follow-up