Maximum Subarray

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Examples

The brute-force approach

Try every possible subarray: for each starting index i and ending index j, compute the sum of nums[i..j] and track the maximum.

max_sum = nums[0]

for i in 0 .. n - 1:
    current = 0
    for j in i .. n - 1:        # ← nested loop is the problem
        current += nums[j]
        max_sum = max(max_sum, current)

return max_sum

O(n²), you're recomputing overlapping sums from scratch for every starting position. For a 10,000-element array, that's 50 million iterations.

Spotting the pattern

This is a Kadane's Algorithm problem. The key question to ask yourself:

At each element, should I extend the current subarray or start a new one?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.