Maximum Subarray
⚡ Difficulty: Medium 🏷️ Topic: Dynamic Programming (Kadane’s)
Given an integer array, find the contiguous subarray with the largest sum and return that sum.
Input
- Line 1: integer
n— the size of the array. - Line 2:
nspace-separated integers (may be negative).
Output
- A single integer: the maximum subarray sum.
Example
Input:
9
-2 1 -3 4 -1 2 1 -5 4
Output:
6
The subarray [4, -1, 2, 1] has the largest sum 6.
—
Your code runs against test cases in a sandbox. Solutions persist in this browser. Read input from stdin, print the answer to stdout.
New to Kadane’s algorithm? See the pattern in the DSA fundamentals or browse all problems.
Discussion
Newest first