Maximum Sum Path in Two Arrays in c#

General
1

To find the maximum sum path in two arrays in C#, you can approach the problem by using two pointers to traverse both arrays simultaneously. The idea is to accumulate the sum of elements from both arrays until you reach a point where the elements differ. At that point, you need to decide which path to take to maximize the sum.

Algorithm Explanation

  1. Initialization: Start with two pointers, one for each array, initialized to the beginning of the arrays. Also, initialize variables to keep track of the current sums of both arrays and the total maximum sum.

  2. Traverse the Arrays: Use a loop to iterate through both arrays. Compare the elements at the current positions of both pointers:

    • If the elements are equal, add the current sums to the total maximum sum, and add the current element to the sum of either array before moving both pointers forward.
    • If one element is less than the other, add the lesser element to the corresponding sum and move that pointer forward.
    • If one element is greater, add the lesser element to the corresponding sum and move that pointer forward.

  3. Finalize the Sum: After exiting the loop, add the remaining sums from both arrays to the total maximum sum.

  4. Return the Result: The total maximum sum represents the maximum sum path through the two arrays.

C# Implementation

Here’s a sample implementation of the above algorithm:

using System;

class Program
{
    static void Main()
    {
        int[] array1 = { 2, 3, 7, 10, 12 };
        int[] array2 = { 1, 5, 7, 8, 10 };

        int maxSum = MaxSumPath(array1, array2);
        Console.WriteLine("Maximum Sum Path: " + maxSum);
    }

    static int MaxSumPath(int[] arr1, int[] arr2)
    {
        int sum1 = 0, sum2 = 0, totalMaxSum = 0;
        int i = 0, j = 0;

        while (i < arr1.Length && j < arr2.Length)
        {
            // If both elements are equal, take the max path
            if (arr1[i] == arr2[j])
            {
                totalMaxSum += Math.Max(sum1 + arr1[i], sum2 + arr2[j]);
                sum1 = 0; // Reset the sum for the next segment
                sum2 = 0;
                i++;
                j++;
            }
            // If element in arr1 is smaller, add it to sum1
            else if (arr1[i] < arr2[j])
            {
                sum1 += arr1[i];
                i++;
            }
            // If element in arr2 is smaller, add it to sum2
            else
            {
                sum2 += arr2[j];
                j++;
            }
        }

        // Add remaining elements
        while (i < arr1.Length)
        {
            sum1 += arr1[i++];
        }
        while (j < arr2.Length)
        {
            sum2 += arr2[j++];
        }

        // Add the maximum of the remaining sums
        totalMaxSum += Math.Max(sum1, sum2);

        return totalMaxSum;
    }
}

Explanation of Code

  1. Input: Two integer arrays (array1 and array2) are defined.
  2. MaxSumPath Function: This function takes the two arrays as input and processes them to find the maximum sum path.
  3. Pointers and Sums: Two pointers (i, j) are used to track the current position in each array. sum1 and sum2 hold the cumulative sums of elements before a common element is reached.
  4. Comparison Logic: The loop handles the comparison of the current elements and updates the sums accordingly. When a common element is found, it calculates the maximum sum for that segment.
  5. Finalization: Remaining elements are processed after the loop ends, and the final maximum sum is returned.

This implementation efficiently computes the maximum sum path while keeping the code clean and understandable.