C#•2y ago

❔ Maximum Subarray Leetcode Help

C#
 public int MaxSubArray(int[] nums) {
        
        //declarations
        int max_ending_here = nums[0];
        int max_so_far = nums[0];

        //logic
        for(int i = 1; i < nums.Length; i++)
        {
            max_ending_here += nums[i];
            if(max_ending_here > max_so_far)
            {
                max_so_far = max_ending_here;
            }
        }

        return max_so_far;
    }

C#
 public int MaxSubArray(int[] nums) {
        
        //declarations
        int max_ending_here = nums[0];
        int max_so_far = nums[0];

        //logic
        for(int i = 1; i < nums.Length; i++)
        {
            max_ending_here += nums[i];
            if(max_ending_here > max_so_far)
            {
                max_so_far = max_ending_here;
            }
        }

        return max_so_far;
    }

I'm getting the wrong answer with test case

nums =
[-2,1,-3,4,-1,2,1,-5,4]

nums =
[-2,1,-3,4,-1,2,1,-5,4]

Im not sure what I should be doing differently but I think I may be misunderstanding something with Kadane's Algorithm and negative numbers

11 Replies

Doombox•2y ago

I have exceptionally vague memories of Kadane's algo

var maxSum = int.MinValue;
var currSum = 0;

for (var i = 0; i < arr.Length; i++) 
{
    currSum += arr[i];
    if (currSum > maxSum)
        maxSum = currSum;
    if (currSum < 0)
        currSum = 0;
}

return maxSum;

var maxSum = int.MinValue;
var currSum = 0;

for (var i = 0; i < arr.Length; i++) 
{
    currSum += arr[i];
    if (currSum > maxSum)
        maxSum = currSum;
    if (currSum < 0)
        currSum = 0;
}

return maxSum;

should do the trick though max should be 6 if I'm reading the array right 4, -1, 2, 1 that code should produce that result

MODiX•2y ago

Doombox#1389

REPL Result: Success

var arr = new[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
var maxSum = int.MinValue;
var currSum = 0;

foreach (var num in arr)
{
    currSum += num;
    if (currSum > maxSum)
        maxSum = currSum;
    if (currSum < 0)
        currSum = 0;
}

Console.WriteLine(maxSum);

var arr = new[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
var maxSum = int.MinValue;
var currSum = 0;

foreach (var num in arr)
{
    currSum += num;
    if (currSum > maxSum)
        maxSum = currSum;
    if (currSum < 0)
        currSum = 0;
}

Console.WriteLine(maxSum);

Console Output

Compile: 572.059ms | Execution: 67.100ms | React with ❌ to remove this embed.

Doombox•2y ago

PandraxiconOP•2y ago

can you explain a bit about why you reset currSum to 0 if it's negative?

Doombox•2y ago

uhh, good question, did the algorithm actually specify that the sum should be non-negative? might just be inventing that one oh wait, no, the sum should always start at 0 of course I doubted myself I should really just google it pepetense

PandraxiconOP•2y ago

what do you mean it should always start at 0?

Doombox•2y ago

the sum of the numbers should always be calculated starting from 0, otherwise it's not much of a sum as an optimisation, if the sum is ever lower than 0, we can safely assume that we need to start calculating the next subarray

PandraxiconOP•2y ago

ooh I see and by doing that, it resets currentMax to be equal to the current Array[i] value in the next iteration of the for loop kind of starting the sum over from there?

Doombox•2y ago

yes, essentially imagine an array like this -4, -5, -3, -1, -10, -3, -1, the max value would always be the smallest single number (-1 in this case), easier to understand the code when you step through it with an array in mind it's a simple enough bit of code that you can essentially run the algorithm in your head, or on a piece of paper at the least https://www.geeksforgeeks.org/csharp-program-for-largest-sum-contiguous-subarray/ a better explanation than I can manage, even walks through an example

PandraxiconOP•2y ago

thank you! I def understand it a lot better now so Here's what I have now:

C#

public int MaxSubArray(int[] nums) {
        
        //declarations
        int globalMax = 0;
        int currentMax = 0;

        //validation
        if(nums.Length == 1)
        return nums[0];

        //logic
        for(int i = 0; i < nums.Length ; i++)
        {
           currentMax += nums[i];
           globalMax = Math.Max(currentMax, globalMax);
           if(currentMax < 0)
           {
               currentMax = 0;
           }
        }

        return globalMax;
    }

C#

public int MaxSubArray(int[] nums) {
        
        //declarations
        int globalMax = 0;
        int currentMax = 0;

        //validation
        if(nums.Length == 1)
        return nums[0];

        //logic
        for(int i = 0; i < nums.Length ; i++)
        {
           currentMax += nums[i];
           globalMax = Math.Max(currentMax, globalMax);
           if(currentMax < 0)
           {
               currentMax = 0;
           }
        }

        return globalMax;
    }

But Im getting an issue when the array is [-2, -1]

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

❔ Maximum Subarray Leetcode Help