MediumTopic: Dynamic Programming & ArraysExpected: O(N) Time • O(1) Space
Maximum Subarray Sum (Kadane)
Given an integer array `nums`, find the contiguous subarray (containing at least one number) with the largest possible sum, and return that sum. A subarray is any contiguous, non-empty run of elements from the array.
Examples
Input: nums = [3, -4, 5, 2, -1, 6, -9]
Output: 12
The subarray [5, 2, -1, 6] sums to 12, which is the largest possible.
Input: nums = [-3]
Output: -3
Input: nums = [2, 3, -1, 5]
Output: 9
Constraints
- 1 <= nums.length <= 3 * 10^4
- -1000 <= nums[i] <= 1000
solution.js
JavaScript (ES6+)Test Execution Results
Input:
[[3,-4,5,2,-1,6,-9]]Expected:
12Your Output:
--