01
02
03
04
05
06
07
08
09
10
11
A
A2Z Sheet

79. Maximum Subarray & The Peak Profit Rollercoaster

Medium
Step 3: Solve Problems on Arrays [Easy -> Medium -> Hard]›Medium

Maximum Subarray & The Peak Profit Rollercoaster

MediumFunction: kadaneSAlgorithm()
ASCI Mission Breakdown • Simple as Hell
"Find the contiguous subarray which has the largest sum and return its sum."
Real-World Metaphor:

Imagine a business running month by month. If accumulated debt wipes you out, you declare bankruptcy on that project and start a fresh venture with clean books. You remember your highest peak profit ever achieved.

Interactive Visual WalkthroughARRAY-POINTERS
Step 1 / 2
Track: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
reset
-2
[0]
1
[1]
-3
[2]
4
[3]
-1
[4]
2
[5]
1
[6]
-5
[7]
4
[8]
Memory Notepad / State Tracker
currentSum:0
maxSum:-2
Mismatch

1. Index 0 (-2 drops below zero)

currentSum = -2. Drops below zero! Reset currentSum to 0.

How to Think About This (Mental Model)

  1. Keep currentSum = 0, maxSum = nums[0].
  2. Iterate through the array: add current number to currentSum.
  3. Update maxSum = Math.max(maxSum, currentSum).
  4. If currentSum < 0, reset currentSum = 0 (cut your losses!).
  5. Return maxSum.

### The Mission Imagine a rollercoaster ride with steep climbs (positive numbers) and sharp drops (negative numbers) along an array: `[-2, 1, -3, 4, -1, 2, 1, -5, 4]`. Your mission is to find the **contiguous track segment** that gives the maximum cumulative elevation gain (maximum sum). If a segment drops your cumulative altitude below zero, you immediately cut your losses, reset to zero, and start climbing fresh!

Examples

Example 1
Input: nums = [1,2,3,4,5]
Output: [1,2,3,4,5]

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
Topic Tags:
Solve Problems on Arrays [Easy -> Medium -> Hard]MediumkadaneSAlgorithm
14px
Ln 1:Col 1
8 lines•120 chars
Spaces: 2•UTF-8
JS(Node v20.12)