Maximum Subarray

easyPRODynamic ProgrammingGoogle DSA

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

Example

Input

-2,1,-3,4,-1,2,1,-5,4

Output

Reasoning

Input: nums is a list of integers, here -2,1,-3,4,-1,2,1,-5,4. A subarray is a contiguous, non-empty run $nums_i, nums_{i+1}, \dots, nums_j$ .
Math: each run has sum $S(i, j) = \sum_{k=i}^{j} nums_k$ , and the answer is the largest $S(i, j)$ over all $i \le j$ .
The best run is indices $3$ to $6$ : $4 + (-1) + 2 + 1 = 6$ . The $-1$ is worth keeping because it connects $4$ to $2 + 1 = 3$ , and $4 - 1 + 3 = 6$ beats $4$ alone or $3$ alone.
Stretching it further only hurts: the values before it, $-2 + 1 + (-3) = -4$ , and after it, $-5 + 4 = -1$ , both add a negative amount.
Output: a single integer, 6. Notice that adding up just the positive values ( $1+4+2+1+4 = 12$ ) is not allowed — they are not contiguous. If every value were negative, the answer would be the single largest (least negative) element, since the run cannot be empty.

Constraints

1 <= len(nums) <= 10^5
-10^4 <= nums[i] <= 10^4

Learn this in

Patterns & MiscellaneousDSA Study Plan

More from Google DSA

Time Based Key-Value Storemedium Moving Average from Data Streameasy Snapshot Arraymedium LRU Cachemedium Find Peak Elementeasy

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results