c# - Why the value of `max` isn't being updated properly? - Stack Overflow

admin管理员组

文章数量:1336140

I was supposed to do it using C#, I am using the window sliding technique to reduce code complexity, but the max variable does not update correctly when the window slides. I made sure that it didn't have any logical error.

The Algorithm

Initialize currentMax = 0
Initialize max = 0
Initialize subArray as an empty HashSet

For each number in numbers (from index 0 to end):
    If number is NOT in subArray:
        Add number to subArray
        Add number to max (sum of the current subarray)
        
        If size of subArray equals subArrayMaxSize:
            Log currentMax, max, and subArray (before removal)
            currentMax = max if max > currentMax else currentMax
            Remove the oldest element from subArray (i - subArray.Count + 1)
            Subtract the removed element from max
            Log currentMax, max, and subArray (after removal)

Return currentMax

The Code I did

int[] numbers = { 1, 5, 4, 2, 9, 9, 9 };
int subArrayMaxSize = 3;

int currentMax = 0, max = 0;
HashSet<int> subArray = new HashSet<int>();

for (int i = 0; i < numbers.Length; i++)
{
    if (!subArray.Contains(numbers[i]))
    {
        subArray.Add(numbers[i]);
        max += numbers[i];

        if (subArray.Count == subArrayMaxSize)
        {
            LogValues(currentMax, max, subArray, true);

            currentMax = Math.Max(currentMax, max);
            subArray.Remove(numbers[i - subArray.Count + 1]);
            max -= numbers[i - subArray.Count + 1];

            LogValues(currentMax, max, subArray, false);
        }
    }
}
void LogValues(int currentMax, int max, HashSet<int> subArray, bool isStart)
{
    if (isStart) Console.WriteLine("======================================================");
    Console.WriteLine($"CurrentMax: {currentMax}, Max: {max}, SubArray: {string.Join(",", subArray)}");
    if (!isStart) Console.WriteLine("\n\n");
}

The output I got

I tried debugging line by line but nothing fruitful.

I was supposed to do it using C#, I am using the window sliding technique to reduce code complexity, but the max variable does not update correctly when the window slides. I made sure that it didn't have any logical error.

The Algorithm

Initialize currentMax = 0
Initialize max = 0
Initialize subArray as an empty HashSet

For each number in numbers (from index 0 to end):
    If number is NOT in subArray:
        Add number to subArray
        Add number to max (sum of the current subarray)
        
        If size of subArray equals subArrayMaxSize:
            Log currentMax, max, and subArray (before removal)
            currentMax = max if max > currentMax else currentMax
            Remove the oldest element from subArray (i - subArray.Count + 1)
            Subtract the removed element from max
            Log currentMax, max, and subArray (after removal)

Return currentMax

The Code I did

int[] numbers = { 1, 5, 4, 2, 9, 9, 9 };
int subArrayMaxSize = 3;

int currentMax = 0, max = 0;
HashSet<int> subArray = new HashSet<int>();

for (int i = 0; i < numbers.Length; i++)
{
    if (!subArray.Contains(numbers[i]))
    {
        subArray.Add(numbers[i]);
        max += numbers[i];

        if (subArray.Count == subArrayMaxSize)
        {
            LogValues(currentMax, max, subArray, true);

            currentMax = Math.Max(currentMax, max);
            subArray.Remove(numbers[i - subArray.Count + 1]);
            max -= numbers[i - subArray.Count + 1];

            LogValues(currentMax, max, subArray, false);
        }
    }
}
void LogValues(int currentMax, int max, HashSet<int> subArray, bool isStart)
{
    if (isStart) Console.WriteLine("======================================================");
    Console.WriteLine($"CurrentMax: {currentMax}, Max: {max}, SubArray: {string.Join(",", subArray)}");
    if (!isStart) Console.WriteLine("\n\n");
}

The output I got

I tried debugging line by line but nothing fruitful.

• c#

Share Improve this question Follow asked Nov 20, 2024 at 1:00 Zubair JamilZubair Jamil 12222 silver badges1010 bronze badges

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 2

After removing an element from subArray HashSet, the number of elements in subArray decreases by 1. Therefore, in your code, the index i - subArray.Count + 1 was shifted to another element of numbers array.

int[] numbers = { 1, 5, 4, 2, 9, 9, 9 };
int subArrayMaxSize = 3;

int currentMax = 0, max = 0;
HashSet<int> subArray = new HashSet<int>();

for (int i = 0; i < numbers.Length; i++)
{
    if (!subArray.Contains(numbers[i]))
    {
        subArray.Add(numbers[i]);
        max += numbers[i];

        if (subArray.Count == subArrayMaxSize)
        {
            LogValues(currentMax, max, subArray, true);

            currentMax = Math.Max(currentMax, max);
            max -= numbers[i - subArray.Count + 1];             // 1
            subArray.Remove(numbers[i - subArray.Count + 1]);   // 2

            LogValues(currentMax, max, subArray, false);
        }
    }
}

Output:

======================================================
CurrentMax: 0, Max: 10, SubArray: 1,5,4
CurrentMax: 10, Max: 9, SubArray: 5,4



======================================================
CurrentMax: 10, Max: 11, SubArray: 2,5,4
CurrentMax: 11, Max: 6, SubArray: 2,4



======================================================
CurrentMax: 11, Max: 15, SubArray: 2,9,4
CurrentMax: 15, Max: 11, SubArray: 2,9

---

The condition isn't quite clear in the row:

Remove the oldest element from subArray (i - subArray.Count + 1)

Does this index refer to subArray or numbers? I hope that it refers to numbers array. Then everything will work without errors, but this is the wrong way to find any values of the sliding window. The fact is that a HashSet can contain only one unique value each, but numbers array can contain duplicates. This will lead to the fact that not the oldest elements will be removed from subArray and subtracted from max.

Let's look at the following sequence:

int[] numbers = { 1, 2, 2, 3, 4 };

The result will be as follows:

======================================================
CurrentMax: 0, Max: 6, SubArray: 1,2,3
CurrentMax: 6, Max: 4, SubArray: 1,3



======================================================
CurrentMax: 6, Max: 8, SubArray: 1,4,3
CurrentMax: 8, Max: 6, SubArray: 1,4,3

That is, the 2nd element (2) is removed instead of the oldest, and then the value 2 cannot be removed from the subArray at all, but is subtracted from max. It was hardly intended that way.

---

If you try to take the 1st element from subArray as the oldest, then keep in mind:
HashSet doesn't guarantee the insertion order, especially after manimulations: delete - insert.

The issue with your max variable not updating properly seems to be caused by the logic inside the loop, particularly in the way you're updating max and handling the sliding window logic. Let's break it down.

Problem Areas:

Incorrect Index Calculation: When you calculate the index for the element to remove from subArray (numbers[i - subArray.Count + 1]), you assume that subArray.Count matches the sliding window's actual position in numbers. However, since subArray is a HashSet, the order of elements is not guaranteed, which causes the wrong element to be removed.

HashSet Limitations: A HashSet is unordered, which means the removal of elements based on a sliding window logic will not work as expected. You cannot ensure that the oldest element is removed when the window size exceeds subArrayMaxSize.

Solution: To fix the issue, replace HashSet with a Queue for maintaining the order of the sliding window. This ensures that the oldest element is always removed, maintaining the logic for sliding the window correctly.

Corrected Code:

  int[] numbers = { 1, 5, 4, 2, 9, 9, 9 };
  int subArrayMaxSize = 3;

  int currentMax = 0, max = 0;
  Queue<int> subArray = new Queue<int>();

  for (int i = 0; i < numbers.Length; i++)
  {
      if (!subArray.Contains(numbers[i]))
      {
          subArray.Enqueue(numbers[i]);
          max += numbers[i];

          if (subArray.Count > subArrayMaxSize)
          {
              LogValues(currentMax, max, subArray, true);

              currentMax = Math.Max(currentMax, max);
              int removed = subArray.Dequeue(); // Remove the oldest element
              max -= removed;

              LogValues(currentMax, max, subArray, false);
          }
      }
  }
  void LogValues(int currentMax, int max, Queue<int> subArray, bool isStart)
  {
      if (isStart) Console.WriteLine("======================================================");
      Console.WriteLine($"CurrentMax: {currentMax}, Max: {max}, SubArray: {string.Join(",", subArray)}");
      if (!isStart) Console.WriteLine("\n\n");
  }

Key Changes:

1. Replaced HashSet with Queue: A Queue ensures the correct order of elements for the sliding window logic.

2. Handled Window Size Properly: The condition subArray.Count > subArrayMaxSize ensures that only when the queue exceeds the maximum size, the oldest element is removed, and the max is updated accordingly.

3. Accurate Sliding Logic: The Dequeue() operation removes the oldest element in the queue, keeping the window logic consistent.

本文标签： cWhy the value of max isn39t being updated properlyStack Overflow