PHANTOM DEV

PHANTOM DEV

Maximum Sub-array Problem

Maximum Sub-array Problem

Subscribe to my newsletter and never miss my upcoming articles

Maximum Sub-array Problem

03 Sep 2021 | 3 min read

The maximum subarray problem is a popular interview question among large corporates. You can find the question in popular platforms like leetcode and hackerrank the question is usually ranked as one of the easy/medium questions. And there are quite a few variations of the questions thrown around different platforms. But the core problem has a lot of industrial applications like computer vision.

Questions from leetcode

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

arr = [-1, 3, 4,-11, 2, 9]

So this question, what is meant by contiguous, is that the sequence of numbers has to be one after the other in the original array. So for an instance, we can't pick [9,4,3,2] and say this is the largest subarray.

Looking at this example array, it's clear that the answer is 11. And the subarray is [2,9]

To solve this problem there are two answers, the most basic approach is to dive into brute force mode and sum each and every subarray you can generate.

function maxSubArray(arr) {
    let max_sum = null;
    for (i=0;i < arr.length;i++) {
        for(j=1; j <= arr.length; j++){
            let subarray = arr.slice(i,j)
            if (subarray.length === 0) { continue; }

            let total = 0
            subarray.map(v => total += v);

            if (max_sum === null || max_sum < total) {
                max_sum = total
            }
        }
    }

    return max_sum;
}

How does this work, the nested loop helps us create a slice of the array and check if the sum of the slice is the max and then returns max_sum at the.

There is no problem with this solution for a small data set. It works fine, but for a larger data set this sucks given the complexity is O(n^2)

But fortunately, this is a solved problem. Kadane's Algorithm is a solution that helps address this problem in linear time O(n)

function maxSum(arr) {
    let max_sum = null;
    let current_sum = null;

    for(i=0; i < arr.length; i++) {
        let e = arr[i];
        current_sum = current_sum ?? e
        max_sum = max_sum ?? e

        let possible_new_sum = i == 0 ? e : current_sum + e;

        // debug: console.log(`max_sum ${max_sum} current_sum ${current_sum} e ${e} possible_new_sum ${possible_new_sum}`);
        // When the current value (e) is greater than the sum of
        // everything upto the current value, we reset the current_sum
        // If its not, we continue to add the value to the current_sum.
        current_sum = Math.max(e, possible_new_sum);
        // deubg: console.log(`e > possible_new_sum ${e > possible_new_sum } current_sum ${current_sum}`);

        // Soon as the current_sum has a value greater than max_sum we replace the max_sum.
        max_sum = Math.max(current_sum, max_sum)
    }

    return max_sum;
}

The code is really simple, to be honest. The core of the algorithm is to make a single pass through the array and to keep the max sum and a running current sum for the current subarray being processed.

Processing the results happens something like this for [-1, 3, 4,-11, 2, 9]the following are the commented-out console logs with the prefix debug in the code snippet above.

Every time e > possible_new_sum is true we reset the current_sum and whenever current_sum becomes bigger than max_sum that means we have found a new subarray that has bigger than what we had found before so we replace it with its value.

The funny bits of prepping code let possible_new_sum = i == 0 ? e : current_sum + e; is to handle the edge case with the first index in the iteration. We haven't gone through a cycle so this will not make sense to be current_sum + e rather it should just be the value of e

When I do these kinds of problems locally, I use a small hack to test different edge cases, it's like a barebones test suite for the problem.

tests = [
    {
        arr: [1,-2,-3,2,5,-11,-2],
        result: 7
    },
    {
        arr: [-1,-3,-9,-11,-2,-10],
        result: -1
    },
    {
        arr: [-7,-3,-9,-11,-2,-10],
        result: -2
    },
    {
        arr: [-1, 3, 4,-11, 2, 9],
        result: 11
    }
]


tests.forEach(test => {
    if (maxSum(test.arr) === test.result) {
        console.log(`${test.arr} passed.`);
    } else {
        console.log(`${test.arr} failed.`);
    }
})

If you need to clarify the underlying concepts with the Kadanes Algorithm you can look into Greedy Algorithms and Iterative Dynamic Programming algorithms.

#interview #Kadanes Algorithm #whiteboarding #algorithms

← Backtracking with N Queens AWS ECS Service with One Task →

 
Share this