Find maximum sum path involving elements of given arrays

Posted in

Find maximum sum path involving elements of given arrays
vinaykhatri

Vinay Khatri
Last updated on May 30, 2024

    Problem

    Given two sorted arrays, where the arrays may share some elements. Find the largest sum path from the beginning of any array to the end of either of the two arrays. Only at common items may we transition from one array to another.

    Approach

    The concept is to compute the sum of elements between all common locations in both arrays. When two sums have a common point, compare them and add the maximum of two to the result. Make variables, as ans , sum1 , sum2 . Set the result to 0. In addition, set the variables sum1 and sum2 to 0. sum1 and sum2 are used to hold the sum of the elements in array 1 and array2, respectively.

    These sums are between two points that have a common element. If the current element of array 1 is smaller than the current element of array 2, then sum1 is updated; otherwise, sum2 is updated if the current element of array 2 is smaller. If the current element of array 1 and array 2 are the same, then add the maximum of sum1 and sum2 to the result. Include the common elements in the final output.

    The time complexity of this approach is O(n+m), where n and m are the sizes of both arrays, respectively.

    C++ Programming

    #include <iostream>
    using namespace std;
    int maxSum(int nums1[], int nums2[], int m, int n)
    {
        int i = 0, j = 0;
    
        // Initialize ans,  and current sums of both arrays
        int ans = 0, sum1 = 0, sum2 = 0;
    
        while (i < m && j < n)
        {
            if (nums1[i] < nums2[j])
                sum1 += nums1[i++];
    
            else if (nums1[i] > nums2[j])
                sum2 += nums2[j++];
    
            else // if we reached a common element
            {
                ans += max(sum1, sum2) + nums1[i];
    
                sum1 = 0;
                sum2 = 0;
        
                i++;
                j++;
    
            }
        }
    
        // Add remaining elements of array 1
        while (i < m)
            sum1 += nums1[i++];
    
        // Add remaining elements of array 2
        while (j < n)
            sum2 += nums2[j++];
    
        ans += max(sum1, sum2);
    
        return ans;
    }
    
    int main(){
        int nums1[] = {1, 2, 2, 3};
        int nums2[] = {1, 8, 2, 1};
        int m = sizeof(nums1)/sizeof(nums1[0]);
        int n = sizeof(nums2)/sizeof(nums2[0]);
        cout<<maxSum(nums1, nums2, m, n);
    }

    Output

    12

    C# Programming

    using System;
    
    public class Solution {
     public static int max(int x, int y) { return (x > y) ? x : y; }
     public static int maxSum(int[] nums1, int[] nums2, int m,
     int n)
     {
    
     // initialize indexes for nums1[]
     // and nums2[]
     int i = 0, j = 0;
    
     // Initialize ans and current sums
     int ans = 0, sum1 = 0, sum2 = 0;
     while (i < m && j < n) {
     // Add elements of nums1[] to sum1
     if (nums1[i] < nums2[j])
     sum1 += nums1[i++];
    
     // Add elements of nums2[] to sum2
     else if (nums1[i] > nums2[j])
     sum2 += nums2[j++];
    
     // we reached a common element
     else {
    
     // Take the maximum of two sums and add to
     // ans
     // Also add the common element of array,
     // once
     ans += max(sum1, sum2) + nums1[i];
    
     // Update sum1 and sum2 for elements after
     // this intersection point
     sum1 = 0;
     sum2 = 0;
    
     // update i and j to move to next element of
     // each array
     i++;
     j++;
     }
     }
    
     // Add remaining elements
     while (i < m)
     sum1 += nums1[i++];
    
     while (j < n)
     sum2 += nums2[j++];
    
     ans += max(sum1, sum2);
    
     return ans;
     }
     public static void Main(string[] args){
         int[] arr1={1, 2, 2, 3};
         int[] arr2={1, 8, 2, 1};
         int m = arr1.Length;
         int n = arr2.Length;
         Console.WriteLine(maxSum(arr1, arr2, m, n));
         
     }
    }

    Output

    12

    C Programming

    #include <stdio.h>
    int min(int a, int b){
        return a>=b?b:a;
    }
    int max(int a, int b){
        return a>=b?a:b;
    }
    int maxSum(int nums1[], int nums2[], int m, int n)
    {
        int i = 0, j = 0;
    
        // Initialize ans,  and current sums of both arrays
        int ans = 0, sum1 = 0, sum2 = 0;
    
        while (i < m && j < n)
        {
            if (nums1[i] < nums2[j])
                sum1 += nums1[i++];
    
            else if (nums1[i] > nums2[j])
                sum2 += nums2[j++];
    
            else // if we reached a common element
            {
                ans += max(sum1, sum2) + nums1[i];
                sum1 = 0;
                sum2 = 0;    
                i++;
                j++;
            }
        }
    
        // Add remaining elements of array 1
        while (i < m)
            sum1 += nums1[i++];
    
        // Add remaining elements of array 2
        while (j < n)
            sum2 += nums2[j++];
        ans += max(sum1, sum2);
        return ans;
    }
    
    int main(){
        int nums1[] = {1, 2, 2, 3};
        int nums2[] = {1, 8, 2, 1};
        int m = sizeof(nums1)/sizeof(nums1[0]);
        int n = sizeof(nums2)/sizeof(nums2[0]);
        printf("%d", maxSum(nums1, nums2, m, n));
    }

    Output

    12

    People are also reading:

    Leave a Comment on this Post

    0 Comments