LC 53 — Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum. The subarray must contain at least one element.

Input: nums = -21-34-121-54
Output: 6
Explanation: The subarray 4-121 has the largest sum 6.
Input: nums = [1]
Output: 1

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

Given nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], find the contiguous subarray with the largest sum. In an interview, you might start here — enumerate every subarray. For 9 elements that is 45 ranges to check. The interviewer nods, then asks: what happens when n = 100,000? The brute force idea: check every possible subarray, track the best. How bad can that be?

nums (9 elements)
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8

Try enumerating subarrays by hand. Tap two cells to define a subarray, or let the system pick a few for you.