#001easyDynamic Programming
Maximum Subarray Sum
Time Limit: 2sMemory: 256MB
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
Loading interactive editor…