C#•2y ago

❔ 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:

C#
public class Solution {
    public int MaxSubArray(int[] nums) {

        int globalMax = nums[0];
        int localMax = 0;

        for(int i = 0; i < nums.Length; i++)
        {
            localMax += nums[i];
            globalMax = Math.Max(localMax, globalMax);
            if(globalMax > localMax)
            {
                localMax = 0;
            }
        }
       return globalMax;
}
}

C#
public class Solution {
    public int MaxSubArray(int[] nums) {

        int globalMax = nums[0];
        int localMax = 0;

        for(int i = 0; i < nums.Length; i++)
        {
            localMax += nums[i];
            globalMax = Math.Max(localMax, globalMax);
            if(globalMax > localMax)
            {
                localMax = 0;
            }
        }
       return globalMax;
}
}

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

4 Replies

mtreit•2y ago

Did you figure it out?

Connor•2y ago

if (globalMax > localMax) localMax = 0 is incorrect because it resets the localMax every time the globalMax is greater than localMax. However, this doesn't mean that the current subarray cannot contribute to a larger sum later in the array. By setting localMax to 0, you're essentially breaking the continuity of the subarray, which is not the intended behavior for this problem. The goal is to find the contiguous subarray with the largest sum, so resetting localMax to 0 prematurely can cause you to miss the actual maximum subarray.

if (localMax < 0)
{
    localMax = 0;
}

if (localMax < 0)
{
    localMax = 0;
}

PandraxiconOP•2y ago

okay I get it now thank you!!!

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ Kadane's Algorithm Help