❔ Kadane's Algorithm Help
I'm working on the Maximum Subarray problem (Given an integer array nums, find the
subarray with the largest sum, and return its sum.) and I think I'm missing something in my understanding of it
Here's what I have so far:
Just walking through my though process:
I have two variables to keep track of the global and local maximum values. I set the global max to the first value in the array and the local to 0, that way when I start iterating through the array, the first check (when i = 0) checks the first value in the array against 0 to account for negative first numbers.
When iterating through the array, I am continuously adding the next array value to the local max and comparing it to the previously largest max (stored in global max), then comparing the two, replacing the GlobalMax value with the larger value.
I then reset localMax to 0 if the localMax value was smaller, starting a new subarray to check.
Once it reaches the end of the array, it returns the globalMax
Let me know if there's anything wrong in my thought process or if I'm missing something
My current code messes up with the following test case: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
it returns 4 instead of 6
subarray with the largest sum, and return its sum.) and I think I'm missing something in my understanding of it
Here's what I have so far:
Just walking through my though process:
I have two variables to keep track of the global and local maximum values. I set the global max to the first value in the array and the local to 0, that way when I start iterating through the array, the first check (when i = 0) checks the first value in the array against 0 to account for negative first numbers.
When iterating through the array, I am continuously adding the next array value to the local max and comparing it to the previously largest max (stored in global max), then comparing the two, replacing the GlobalMax value with the larger value.
I then reset localMax to 0 if the localMax value was smaller, starting a new subarray to check.
Once it reaches the end of the array, it returns the globalMax
Let me know if there's anything wrong in my thought process or if I'm missing something
My current code messes up with the following test case: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
it returns 4 instead of 6
