Maximum Subarray Kadane
Problem Description
Given an integer array `sequence`, find the contiguous subarray (containing at least one element) that has the largest sum and return that sum.
A **subarray** is a contiguous part of an array.
**Example 1:**
```
Input: sequence = [-2, 3, -1, 4, -5, 6, -3]
Output: 7
Explanation: The subarray [3, -1, 4, -5, 6] sums to 7, which is the maximum.
Actually [3, -1, 4] = 6 and [4, -5, 6] = 5 and [3, -1, 4, -5, 6] = 7. Output: 7.
```
**Example 1:**
```
Input: sequence = [-2, 3, -1, 4, -5, 6, -3]
Output: 7
Explanation: The subarray [3, -1, 4, -5, 6] has the largest sum = 7.
```
**Example 2:**
```
Input: sequence = [-8, -3, -6, -2, -5]
Output: -2
Explanation: All elements are negative; the least-negative element -2 is the answer.
```
Constraints
- 1 <= sequence.length <= 10^5
- -10^4 <= sequence[i] <= 10^4
Follow-up
Can you also return the start and end indices of the maximum subarray, and handle the case where you must choose exactly k non-overlapping subarrays?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.