All DSA problems
MediumArraysAmazonMicrosoftApple
Maximum Subarray (Kadane)
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and print that sum.
**Input**
First line: n
Second line: n integers
Examples
Example 1
Input:
9 -2 1 -3 4 -1 2 1 -5 4
Output: 6
Subarray [4,-1,2,1] has sum 6
Example 2
Input:
1 1
Output: 1
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Target: O(n) time · O(1) space