I want to do a variation of the get Maximum subarray from leetcode in which I collect the entire maximum subarray as well, but I can't seem to figure out what I'm missing.
var maxSubArray = function(nums) {
let currSum = 0;
let maxSum = -Infinity;
let currArray = [];
let maxArray = [];
for (let i = 0; i < nums.length; i++) {
currSum += nums[i];
if (Math.max(currSum, maxSum) != maxSum) {
maxArray = currArray;
maxSum = currSum;
currArray.push(nums[i]);
}
maxSum = Math.max(currSum, maxSum);
if (currSum < 0) {
currSum = 0;
currArray = []
}
}
console.log(maxArray);
return maxSum;
};
I recognize why this is wrong, as the currSum value cannot have a negative component because it'd always be a lower sum than the current maxSum. But I'm not sure what condition it would require for this. I feel like I'm missing something obvious but cannot think of it :(
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
I was going about it the wrong way as I was storing an array when I could have just stored the index.
var maxSubArray = function(nums) {
let currSum = 0;
let maxSum = -Infinity;
let prevMax = -Infinity;
let start = 0;
let end = 0;
for (let i = 0; i < nums.length; i++) {
currSum += nums[i];
if (nums[i] > maxSum) {
start = i;
}
if (Math.max(currSum, maxSum) != maxSum) {
maxSum = currSum;
end = i;
}
if (currSum < 0) {
currSum = 0;
if (nums[i+1] != undefined) {
start = i+1;
}
}
}
console.log(start, end);
console.log(nums.slice(start, end+1))
return maxSum;
};