Grind 75 Question 10: Maximum Subarray
In which I spend way too long on a problem I need to just admit I need help on.
The Problem
The First Attempts
I think I can identify this one as a two-pointer, but beyond that I’m having trouble deciding how to execute it. Here’s the initial whiteboarded failure:
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let pointerOne = 0;
let pointerTwo = 1;
let maximumNumber = 0;
while(pointerOne < nums.length) {
let tempTotal = nums.reduce(pointerOne, pointerTwo);
Math.max(maximumNumber, tempTotal);
if(nums[pointerTwo + 1] < 1) {
pointerTwo + 2;
};
if(nums[pointerOne + 1] < 0) {
pointerOne + 2;
}
};
return maximumNumber;
};
My first problem is that I’m not using array.reduce properly — a quick W3Schools search reminds me that it needs to execute a function. It seems like a big old waste of time to continually be calculating the sum total of an array, so I try to calculate and then subtract…
I waste most of a day on code that just doesn’t work. Here’s an example:
var maxSubArray = function(nums) {
let pointerOne = 0;
let pointerTwo = nums.length - 1
let runningTotal = nums.reduce(arrayTotal)
let maximumNumber = 0;
function arrayTotal(total, num) {
return total + num
}
while(pointerOne < nums.length) {
if((nums[pointerOne] > 0) && (runningTotal -= nums[pointerOne] > maximumNumber)){
maximumNumber = runningTotal -= nums[pointerOne]
pointerOne ++;
} else {
pointerOne ++;
};
if((nums[pointerTwo] > 0) && (runningTotal -= nums[pointerTwo] > maximumNumber)) {
maximumNumber = runningTotal -= nums[pointerTwo]
pointerTwo --;
} else {
pointerTwo --;
}
};
return maximumNumber;
};I try to brute-force it next, because why not? The following works, until I try to submit it and Leetcode throws an utterly ridiculous (yet, probably realistic) testcase at it that’s just…numbers on numbers on numbers.
var maxSubArray = function(nums) {
let maximumNumber = nums[0];
let runningTotal = 0;
for(i = 0; i < nums.length; i++){
for(j = i; j < nums.length; j++){
runningTotal += nums[j];
maximumNumber = Math.max(runningTotal, maximumNumber)
};
runningTotal = 0;
}
return maximumNumber;
};Time to swallow my pride and visit Neetcode yet again.
The Solution
Turns out, my initial attempt of using two pointers wasn’t too far off, but it needed some tweaking to get it right. And…not two pointers, exactly. Oops.
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let maximumNumber = nums[0];
let runningTotal = 0;
for(i = 0; i < nums.length; i++){
if(runningTotal < 0){
runningTotal = 0;
}
runningTotal += nums[i];
maximumNumber = Math.max(maximumNumber, runningTotal)
}
return maximumNumber;
};So here’s the code, explained.
- First, we declare maximumNumber to be returned at the end, and initialize it as nums[0] because why not? That is what the maximum number will start out as.
- We also declare a runningTotal, starting as zero. This will be what we compare the maximumNumber against each time we add a number in nums to the subarray.
- Next, we run through each number in nums.
- If runningTotal is less than zero, we reset it to zero, essentially updating our ghost pointerOne to the current nums[i]. This is one of the bits I was attempting but missing the mark on execution. If I have an array of [1, -3, 22] the return will be 22. Because 1 and -3 add up to a sum total of -2, that’s going to take away from the rest of the subarray. So we axe it, and we’re left with 0 to add 22 to. If that makes any sense at all.
- After all that, we add nums[i] to runningTotal.
- Then, we find the maximum number between maximumNumber and running total.
- This is repeated until we reach the end of the array.
- Finally maximumNumber is returned.
What I Learned
Hmm. I don’t think I learned any big useful concepts, though I did discover that where you put the if runningTotal < 0 statement matters! I was doing it after adding nums[i], which made test cases like [-1] and [-2, 1] return incorrectly.
But also, I think this was the first Leetcode Medium question I’ve done! That’s an accomplishment! Here’s to many more. Which I can accomplish. Without brute-force. But maybe probably with the help of Neetcode.
mins
read
