DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Maximum Subarray (Kadane's Algorithm)

MediumArraysDynamic Programming
AmazonMicrosoftAppleGoldman Sachs Community-reported practice tags — not verified company questions.

1Problem statement

Given an integer array nums, find the contiguous subarray (containing at least one number) with the largest sum and return that sum.

2Examples

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.
Input: nums = [1]
Output: 1
Input: nums = [5, 4, -1, 7, 8]
Output: 23

3Constraints

  • 1 ≤ nums.length ≤ 10⁵
  • −10⁴ ≤ nums[i] ≤ 10⁴

4Approaches

Approach 1

Brute Force

Try every start and end index and sum each subarray.

Time O(n³) (O(n²) with running sums)Space O(1)

Approach 2

Better: Divide and Conquer

Best subarray is in the left half, the right half, or crosses the middle.

Time O(n log n)Space O(log n)

Approach 3

Optimal: Kadane's Algorithm

best ending here = max(num, best ending at previous + num). Track the overall maximum.

Time O(n)Space O(1)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

function maxSubArray(nums) {
  let current = nums[0];
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubArray([1]));
console.log(maxSubArray([5, 4, -1, 7, 8]));

6Complexity

Time

O(n)

Space

O(1)

7Visual walkthrough

  1. 1.current = -2, best = -2
  2. 2.num 1: current = max(1, -2 + 1) = 1, best = 1
  3. 3.num -3: current = max(-3, 1 - 3) = -2
  4. 4.num 4: current = max(4, -2 + 4) = 4, best = 4
  5. 5.num -1, 2, 1: current = 3, 5, 6 → best = 6
  6. 6.num -5, 4: current = 1, 5 → best stays 6

8Related questions

Climbing StairsTwo Sum

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions