Difficulty: MediumGreedy

Maximum Subarray

Problem in Plain English

Given an integer array, find the largest possible sum of any contiguous block inside it. The block must contain at least one element and may be the whole array.

Problem Statement

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. A subarray must keep the original order and stay unbroken.

For nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] the answer is 6 from the block [4, -1, 2, 1]. A single element also counts, so nums = [1] returns 1.

Constraints

$1 \leq n = \mathrm{nums.length} \leq 10^5$ .
$-10^4 \leq \mathrm{nums}[i] \leq 10^4$ .
The chosen subarray must contain at least one element.

Examples

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

The block [4, -1, 2, 1] sums to 6, the largest of any contiguous block.

Example 2

Input: nums = [1]
Output: 1

The only block is [1] itself.

Example 3

Input: nums = [5, 4, -1, 7, 8]
Output: 23

The whole array sums to 23, which beats every shorter block.

Example 4

Input: nums = [-3, -1, -2]
Output: -1

A nonempty block is required. The single value -1 beats every longer block; choosing an empty block with sum zero is illegal.

Intuition

A contiguous block cannot skip a negative value in its middle, but it can discard a harmful prefix. In Example 1, the sum before 4 is negative, so starting fresh at 4 beats extending it. The later -1 stays inside [4, -1, 2, 1] because the running sum remains positive and can help the next value. Track both the best block ending at the current index and the best block seen anywhere; these are different quantities.

Approaches

All Subarrays Scan

Solution Details

Reveal All Subarrays Scan: intuition, complexity, and code

Intuition

Anchor a start index and extend the end one step at a time, tracking the running total and the best total seen. Checking every start and end pair cannot miss the answer, but each start re-adds the same tail elements.

Step-by-Step Logic

Initialize best with the first element, so an all-negative array still has a legal nonempty answer. Example 1 starts with best = -2.
For each start index, reset total = 0; extend the end from that start through the array, adding each new value once. Every such running total represents a nonempty contiguous block.
After each addition update best. Example 1 starts 0, 1, and 2 attain maxima 2, 4, and 3, so best is 4 when start 3 begins.
Repeat for every later start. Start 3 also reaches 6 from [4, -1, 2, 1]; no block beats that total, so return 6.

Why It Works

Each legal nonempty subarray has a unique start i and end j with i no larger than j. The outer loop visits every start and the inner loop visits every valid end. Before comparing a block, total equals the sum from i through j because it starts at zero and receives each element in that interval exactly once. Updating best retains the largest examined sum. After the loops all nonempty intervals have been examined, so best is the global maximum. Seeding with a real element prevents an empty interval from winning on negative inputs.

Dry Run

All Subarrays Scan: variable states at each step
start `i`	end `j`	added	`total` before → after	`best` before → after
0	0	-2	0 → -2 (reset before this start)	-2 → -2
0	1	1	-2 → -1	-2 → -1
0	2	-3	-1 → -4	-1 → -1
0	3	4	-4 → 0	-1 → 0
0	4	-1	0 → -1	0 → 0
0	5	2	-1 → 1	0 → 1
0	6	1	1 → 2	1 → 2
0	7	-5	2 → -3	2 → 2
0	8	4	-3 → 1	2 → 2
1	1	1	0 → 1 (reset before this start)	2 → 2
1	2	-3	1 → -2	2 → 2
1	3	4	-2 → 2	2 → 2
1	4	-1	2 → 1	2 → 2
1	5	2	1 → 3	2 → 3
1	6	1	3 → 4	3 → 4
1	7	-5	4 → -1	4 → 4
1	8	4	-1 → 3	4 → 4
2	2	-3	0 → -3 (reset before this start)	4 → 4
2	3	4	-3 → 1	4 → 4
2	4	-1	1 → 0	4 → 4
2	5	2	0 → 2	4 → 4
2	6	1	2 → 3	4 → 4
2	7	-5	3 → -2	4 → 4
2	8	4	-2 → 2	4 → 4
3	3	4	0 → 4 (reset before this start)	4 → 4
3	4	-1	4 → 3	4 → 4
3	5	2	3 → 5	4 → 5
3	6	1	5 → 6	5 → 6
3	7	-5	6 → 1	6 → 6
3	8	4	1 → 5	6 → 6
4	4	-1	0 → -1 (reset before this start)	6 → 6
4	5	2	-1 → 1	6 → 6
4	6	1	1 → 2	6 → 6
4	7	-5	2 → -3	6 → 6
4	8	4	-3 → 1	6 → 6
5	5	2	0 → 2 (reset before this start)	6 → 6
5	6	1	2 → 3	6 → 6
5	7	-5	3 → -2	6 → 6
5	8	4	-2 → 2	6 → 6
6	6	1	0 → 1 (reset before this start)	6 → 6
6	7	-5	1 → -4	6 → 6
6	8	4	-4 → 0	6 → 6
7	7	-5	0 → -5 (reset before this start)	6 → 6
7	8	4	-5 → -1	6 → 6
8	8	4	0 → 4 (reset before this start)	6 → 6
finished	none	none	last total `4`	return `6`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

For n elements the loops perform exactly n(n + 1)/2 additions and comparisons, hence quadratic time. The running total, best and loop indices occupy constant auxiliary space; no sliced subarray or input copy is allocated. At n = 100000, a block sum lies between -1000000000 and 1000000000, within Java int and exact JavaScript integer range. The quadratic version is educational and impractical at that maximum n.

Code

Solution.java

1class Solution {2    public int maxSubArray(int[] nums) {3        int best = nums[0];4        for (int i = 0; i < nums.length; i++) {5            // Reset only when the start changes; each addition grows one interval.6            int total = 0;7            for (int j = i; j < nums.length; j++) {8                total += nums[j];9                best = Math.max(best, total);10            }11        }12        return best;13    }14}

Hints

Hint 1

Decide for each position whether the best block ending there extends the past or starts over.

Hint 2

Ask when carrying the running total forward can only hurt the future.

Hint 3

Track the best value seen at any ending instead of remembering where blocks began.

Edge Cases

All numbers negative, as in [-3, -1, -2], where the answer is the largest single element -1.
Single element [1], where the only block is the answer.
Entire array positive, where the answer is the whole-array sum.

Common Mistakes and Interview Tips

Initializing best to zero admits an empty block and fails on [-3, -1, -2]. Seed it with an actual element.
Resetting a negative total before recording it as a candidate can lose the largest negative element. This code resets before adding and updates best immediately after adding.
Returning the final cur reports only the best block ending at the last index. Example 1 ends at 5 but the answer is 6.
Dropping every negative value changes the problem to a subsequence. The optimal block may include negatives such as -1 in Example 1.

Key Takeaway

When segments must stay contiguous, restart the running total the moment it turns negative and remember the best ending anywhere.