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
Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.
Asked at: Jane Street, Citadel, Two Sigma