Maximum subarray sum
Given an integer array, describe an algorithm to find the maximum sum of any contiguous subarray (Kadane's algorithm). What is the max subarray sum of [-2, 1, -3, 4, -1, 2, 1, -5, 4]?
Show hints (2)+
- Track the best subarray ending at each index.
- Reset the running sum when it goes negative.
Answer
Reveal answer →Final answer
6
Create a free account to see the full worked solution and track your progress.
Interview format: Market Maker, Hedge Fund Quant, Systematic & Data-Driven Trading