easyGreedyPure DSA~13 min
Peak Revenue Streak
Daily net revenue can be positive or negative. Find the single contiguous run of days with the largest total — the most profitable streak to highlight on the dashboard.
Problem
Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum, and return that sum.
Input
An array nums of length n (1 ≤ n ≤ 10^5), values in [-10^4, 10^4].
Output
An integer — the maximum contiguous subarray sum.
Constraints
- The subarray must be non-empty
- Values may be negative
- Single pass, O(1) extra space expected
Examples
Example 1
Input
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output
6
The subarray [4, -1, 2, 1] sums to 6.
Example 2
Input
nums = [-3, -1, -2]
Output
-1
All negative; the best single element is -1.