Find maximum sum path involving elements of given arrays

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:

• Print the truth table for XY+Z
• WAP to print the 1 to 10 Multiples of a Number
• Calculate the Factorial of an Integer
• Print the sum of first n natural numbers
• Calculate the sum of two numbers
• Print the ASCII value of a character
• Display a message on screen
• Calculate Simple Interest
• Check whether the entered number is prime or not
• WAP to find the greatest number among the three numbers