#001easyDynamic Programming
Maximum Subarray Sum
Problem
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
This is a classic problem that appears frequently in quant interviews. You should know Kadane's Algorithm by heart.
Input Format
A single line containing space-separated integers.
Output Format
A single integer representing the maximum subarray sum.
Examples
Example 1
Input(A single line containing space-separated integers.)
-2 1 -3 4 -1 2 1 -5 4
Output
6
The subarray [4, -1, 2, 1] has the largest sum = 6.
Example 2
Input(A single line containing space-separated integers.)
1
Output
1
Single element arrays always return that element.
Constraints
- •1 ≤ nums.length ≤ 10^5
- •-10^4 ≤ nums[i] ≤ 10^4
Execution limits: 2s · 256MB
Loading interactive editor…