Skip to content
Get started

Maximum subarray sum

Given an integer array, describe an O(n)O(n) 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)+
  1. Track the best subarray ending at each index.
  2. Reset the running sum when it goes negative.

Answer

Reveal 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

Related questions