Coding

Kadane's Algorithm

Asked at

Atlassian

Google

HashedIn

Ninjacart

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array nums, find the subarray with the largest sum and return the sum of the elements present in that subarray.

A subarray is a contiguous non-empty sequence of elements within an array.

Input: nums = [2, 3, 5, -2, 7, -4] Output: 15 Explanation: The subarray from index 0 to index 4 has the largest sum = 15

Input: nums = [-2, -3, -7, -2, -10, -4] Output: -2 Explanation: The element on index 0 or index 3 make up the largest sum when taken as a subarray

Input: nums = [-1, 2, 3, -1, 2, -6, 5]

1 <= nums.length <= 105
-104 <= nums[i] <= 104

cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
    }
};

java

class Solution {
    public int maxSubArray(int[] nums) {
        
    }
}

python

class Solution:
    def maxSubArray(self, nums):

javascript

class Solution {
    maxSubArray(nums) {

    }
}

csharp

public class Solution {
    /**
     * Given an integer array nums, find the subarray with the largest sum and return its sum.
     */
    public int MaxSubArray(List<int> nums) {
        
    }
}

func maxSubArray(nums []int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Track the best sum of a non-empty subarray ending at the current index.
02Choose between starting at the current value and extending the previous ending sum.
03Update a global maximum from every ending position.
04Initialize from the first element so all-negative inputs remain correct.

Reference answer

Let ending be the maximum sum of a non-empty subarray that ends at the current element. For each value x, either the optimal subarray starts fresh at x or extends the previous one, so update ending = max(x, ending + x). Maintain best = max(best, ending) across the scan. Initialize both variables to the first array value rather than zero; otherwise an all-negative array would incorrectly return an empty subarray with sum zero. The invariant covers every candidate because every non-empty subarray has a final index, and ending stores the best candidate for that final index. Time is O(n) and extra space is O(1). To return boundaries, also track the tentative start whenever x is chosen over ending + x, and save that start and the current index whenever the global best improves.

Then expect these follow-ups

How would you return the subarray boundaries?
Tests: state reconstruction
How would you find the maximum circular subarray?
Tests: pattern extension

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question