Leetcode diary: 53. Maximum Subarray

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

Oh boy the classic! This is probably one of the first problems on leetcode that makes all programers encounter to realize that they are in one hell of an industry. How the fuck are you suppose to solve this first time seeing it?!?!?!?!?? I don't know, I didn't for sure, and hopefully something in this article here today can help you understand this better.

the question is to find the subarray that has the maximum sum. You could do via brute force where you start from an index and find the total sum after adding all the indexes after.

let max = -Infinity;
for (let i=0; i<nums.length; i++) {
    let sum = nums[i];
    for (let j=i+1; j<nums.length; j++) {
        sum+= nums[j];
        max = Math.max(sum)
    }
}

This would surely get you the answer, except it performs just okay, at O(N^2). You could do better.

you can't sort the array, so definitely not NlogN solution. Searching doesn't work...it just don't make sense in the context.

So you are left with O(N) approach, aka iteration.

In the case of [1,2,3,4,5,6,67,8,9,10], you would just keep adding to current sum and updating the max. Easy peasy lemon squeezy.

In the case of [1,-2,-3,-4,-5,-6,-8], the sum just keeps getting smaller, but can still run the same naive approach and get the same answer.

The interesting is what if you have the two cases combined?
[1,2,3,4,5,6,67,8,9,10,1,-2,-3,-4,-5,-6,-8]
for this case... we don't need to change anything right? The same simple adding to current sum and check against max still works, however...

[1,-2,-3,-4,-5,-6,-8, 777, 2,3,4,5,6,67,8,9,10]
then do you still keep adding the sum while going through it iteratively? The obvious answer is when you run into 777, you "ignore" whatever has happened previously and start anew. In other words you are just running the naive approach except treating the 1 array as if they are two different arrays.

So the question is when do you reset? Let's go back to the 777 array. Why do you ignore anything before 777? Because the sum prior to it is not helpful right? They are making the sum smaller, instead of bigger, so why keep them? The answer is then that:
you reset the sum when the (sum+current_number) is smaller than the current_number itself

the full code below:

var maxSubArray = function(nums) {
    let max = Number.MIN_SAFE_INTEGER;
    let curr = 0;
    nums.forEach(function(num){
        curr = num > curr+num ? num : curr + num;
        max = Math.max(max, curr);
    });

    return max;
};

If you cannot come up with this without looking at the solution, don't feel bad. I doubt anyone reading this could the first time. The lesson here is not really the algorithm itself, since this is probably the only problem you'll ever use this. The lesson here is really about the process.

When you are stuck at the problem try out all of possible scenarios. We started out with a naive approach that obviously works for all positive integers. Then the next intuitive thing is to check if it still works against all negative integers. It does, great! We make it harder and imagine what if it's positive then negative. The code still works amazingly. Finally we look at negative then positive. The code does not work, so we need to modify it just a bit since it has been working out pretty well.

Honestly if you never had this problem and come to this point, even if you don't come up with the solution in time it'd be fine with me if I was your interviewer. You obviously haven't been doing leetcode that much, but you were very methodical and systematic with the analysis. That alone is impressive enough, I did not learn to think like this until suffering through a discrete math course... Curse and thanks to my professor :( ...

Let me know anything on your mind after reading through this, THANKS!