Pandraxicon Posts - Answer Overflow

Pandraxicon

•Created by Pandraxicon on 5/3/2023 in #help

❔ 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

5 replies

CC#

•Created by Pandraxicon on 5/1/2023 in #help

❔ 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

25 replies

CC#

•Created by Pandraxicon on 4/28/2023 in #help

TwoSum Help

This is what I have so far:

C#
public class Solution {
    public int[] TwoSum(int[] nums, int target) {

        //declarations
        
        var usedPairs = new Dictionary <int, int>(){};
        int complement = 0;

        //traversal
        for(int i = 0; i<nums.Length; i++)
        {
            complement = target - nums[i];
            if(usedPairs.TryGetValue(complement, out int secondIndex))
            {
                return new int[]{i, secondIndex};
            }
            usedPairs[nums(i)] = i;
        }
        return new int[]{};
        
    }
}

C#
public class Solution {
    public int[] TwoSum(int[] nums, int target) {

        //declarations
        
        var usedPairs = new Dictionary <int, int>(){};
        int complement = 0;

        //traversal
        for(int i = 0; i<nums.Length; i++)
        {
            complement = target - nums[i];
            if(usedPairs.TryGetValue(complement, out int secondIndex))
            {
                return new int[]{i, secondIndex};
            }
            usedPairs[nums(i)] = i;
        }
        return new int[]{};
        
    }
}

I'm getting the following error:

Line 17: Char 23: error CS0149: Method name expected (in Solution.cs)

Line 17: Char 23: error CS0149: Method name expected (in Solution.cs)

with Line 17 being the line with

  usedPairs[nums(i)] = i;

  usedPairs[nums(i)] = i;

I'm not sure exactly what is wrong with this line

10 replies

Gaming

Programming