# Find maximum sum path involving elements of given arrays

By | November 17, 2021

## 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 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++;
}
}

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`