# Maximum Sum Path in Two Arrays

Given two sorted arrays, such that the arrays may have some common elements. Find the sum of the maximum sum path to reach from the beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements. **Note: **The common elements do not have to be at the same indexes.

**Expected Time Complexity: O(m+n)**, where m is the number of elements in ar1[] and n is the number of elements in ar2[].

**Examples:**

Input:ar1[] = {2, 3, 7, 10, 12} ar2[] = {1, 5, 7, 8}Output:35Explanation:35 is sum of 1 + 5 +7+ 10 + 12. We start from the first element of arr2 which is 1, then we move to 5, then 7. From 7, we switch to ar1 (as 7 is common) and traverse 10 and 12.Input:ar1[] = {10, 12} ar2 = {5, 7, 9}Output:22Explanation:22 is the sum of 10 and 12. Since there is no common element, we need to take all elements from the array with more sum.Input:ar1[] = {2, 3, 7, 10, 12, 15, 30, 34} ar2[] = {1, 5, 7, 8, 10, 15, 16, 19}Output:122Explanation:122 is sum of 1, 5,7, 8,10, 12,15, 30, 34

** Efficient Approach:** The idea is to do something similar to merge process of merge sort. This involves calculating the sum of elements between all common points of both arrays. Whenever there is a common point, compare the two sums and add the maximum of two to the result.

__Algorithm__:

- Create some variables,
*result*,*sum1*,*sum2*. Initialize result as 0. Also initialize two variables sum1 and sum2 as 0. Here sum1 and sum2 are used to store sum of element in ar1[] and ar2[] respectively. These sums are between two common points. - Now run a loop to traverse elements of both arrays. While traversing compare current elements of array 1 and array 2 in the following order.
- If current element of
*array 1*is smaller than current element of*array 2*, then update*sum1*, else if current element of*array 2*is smaller, then update*sum2*. - If the current element of
*array 1*and*array 2*are same, then take the maximum of sum1 and sum2 and add it to the result. Also add the common element to the result. - This step can be compared to the merging of two
*sorted*arrays, If the smallest element of the two current array indices is processed then it is guaranteed that if there is any common element it will be processed together. So the sum of elements between two common elements can be processed.

- If current element of

Below is the implementation of the above code:

## C++

`// C++ program to find maximum sum path` `#include <iostream>` `using` `namespace` `std;` `// Utility function to find maximum of two integers` `int` `max(` `int` `x, ` `int` `y) { ` `return` `(x > y) ? x : y; }` `// This function returns the sum of elements on maximum path` `// from beginning to end` `int` `maxPathSum(` `int` `ar1[], ` `int` `ar2[], ` `int` `m, ` `int` `n)` `{` ` ` `// initialize indexes for ar1[] and ar2[]` ` ` `int` `i = 0, j = 0;` ` ` `// Initialize result and current sum through ar1[] and` ` ` `// ar2[].` ` ` `int` `result = 0, sum1 = 0, sum2 = 0;` ` ` `// Below 3 loops are similar to merge in merge sort` ` ` `while` `(i < m && j < n)` ` ` `{` ` ` `// Add elements of ar1[] to sum1` ` ` `if` `(ar1[i] < ar2[j])` ` ` `sum1 += ar1[i++];` ` ` `// Add elements of ar2[] to sum2` ` ` `else` `if` `(ar1[i] > ar2[j])` ` ` `sum2 += ar2[j++];` ` ` `else` `// we reached a common point` ` ` `{` ` ` `// Take the maximum of two sums and add to` ` ` `// result` ` ` `//Also add the common element of array, once` ` ` `result += max(sum1, sum2) + ar1[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 of ar1[]` ` ` `while` `(i < m)` ` ` `sum1 += ar1[i++];` ` ` `// Add remaining elements of ar2[]` ` ` `while` `(j < n)` ` ` `sum2 += ar2[j++];` ` ` `// Add maximum of two sums of remaining elements` ` ` `result += max(sum1, sum2);` ` ` `return` `result;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `ar1[] = { 2, 3, 7, 10, 12, 15, 30, 34 };` ` ` `int` `ar2[] = { 1, 5, 7, 8, 10, 15, 16, 19 };` ` ` `int` `m = ` `sizeof` `(ar1) / ` `sizeof` `(ar1[0]);` ` ` `int` `n = ` `sizeof` `(ar2) / ` `sizeof` `(ar2[0]);` ` ` ` ` `// Function call` ` ` `cout << ` `"Maximum sum path is "` ` ` `<< maxPathSum(ar1, ar2, m, n);` ` ` `return` `0;` `}` |

## Java

`// JAVA program to find maximum sum path` `class` `MaximumSumPath` `{` ` ` `// Utility function to find maximum of two integers` ` ` `int` `max(` `int` `x, ` `int` `y) { ` `return` `(x > y) ? x : y; }` ` ` `// This function returns the sum of elements on maximum` ` ` `// path from beginning to end` ` ` `int` `maxPathSum(` `int` `ar1[], ` `int` `ar2[], ` `int` `m, ` `int` `n)` ` ` `{` ` ` `// initialize indexes for ar1[] and ar2[]` ` ` `int` `i = ` `0` `, j = ` `0` `;` ` ` `// Initialize result and current sum through ar1[]` ` ` `// and ar2[].` ` ` `int` `result = ` `0` `, sum1 = ` `0` `, sum2 = ` `0` `;` ` ` `// Below 3 loops are similar to merge in merge sort` ` ` `while` `(i < m && j < n)` ` ` `{` ` ` `// Add elements of ar1[] to sum1` ` ` `if` `(ar1[i] < ar2[j])` ` ` `sum1 += ar1[i++];` ` ` `// Add elements of ar2[] to sum2` ` ` `else` `if` `(ar1[i] > ar2[j])` ` ` `sum2 += ar2[j++];` ` ` `// we reached a common point` ` ` `else` ` ` `{` ` ` `// Take the maximum of two sums and add to` ` ` `// result` ` ` `//Also add the common element of array, once` ` ` `result += max(sum1, sum2) + ar1[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 of ar1[]` ` ` `while` `(i < m)` ` ` `sum1 += ar1[i++];` ` ` `// Add remaining elements of ar2[]` ` ` `while` `(j < n)` ` ` `sum2 += ar2[j++];` ` ` `// Add maximum of two sums of remaining elements` ` ` `result += max(sum1, sum2);` ` ` `return` `result;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `MaximumSumPath sumpath = ` `new` `MaximumSumPath();` ` ` `int` `ar1[] = { ` `2` `, ` `3` `, ` `7` `, ` `10` `, ` `12` `, ` `15` `, ` `30` `, ` `34` `};` ` ` `int` `ar2[] = { ` `1` `, ` `5` `, ` `7` `, ` `8` `, ` `10` `, ` `15` `, ` `16` `, ` `19` `};` ` ` `int` `m = ar1.length;` ` ` `int` `n = ar2.length;` ` ` ` ` `// Function call` ` ` `System.out.println(` ` ` `"Maximum sum path is :"` ` ` `+ sumpath.maxPathSum(ar1, ar2, m, n));` ` ` `}` `}` `// This code has been contributed by Mayank Jaiswal` |

## Python

`# Python program to find maximum sum path` `# This function returns the sum of elements on maximum path from` `# beginning to end` `def` `maxPathSum(ar1, ar2, m, n):` ` ` `# initialize indexes for ar1[] and ar2[]` ` ` `i, j ` `=` `0` `, ` `0` ` ` `# Initialize result and current sum through ar1[] and ar2[]` ` ` `result, sum1, sum2 ` `=` `0` `, ` `0` `, ` `0` ` ` `# Below 3 loops are similar to merge in merge sort` ` ` `while` `(i < m ` `and` `j < n):` ` ` `# Add elements of ar1[] to sum1` ` ` `if` `ar1[i] < ar2[j]:` ` ` `sum1 ` `+` `=` `ar1[i]` ` ` `i ` `+` `=` `1` ` ` `# Add elements of ar2[] to sum2` ` ` `elif` `ar1[i] > ar2[j]:` ` ` `sum2 ` `+` `=` `ar2[j]` ` ` `j ` `+` `=` `1` ` ` `else` `: ` `# we reached a common point` ` ` `# Take the maximum of two sums and add to result` ` ` `result ` `+` `=` `max` `(sum1, sum2) ` `+` `ar1[i]` ` ` `#update sum1 and sum2 to be considered fresh for next elements` ` ` `sum1 ` `=` `0` ` ` `sum2 ` `=` `0` ` ` `#update i and j to move to next element in each array` ` ` `i ` `+` `=` `1` ` ` `j ` `+` `=` `1` ` ` ` ` `# Add remaining elements of ar1[]` ` ` `while` `i < m:` ` ` `sum1 ` `+` `=` `ar1[i]` ` ` `i ` `+` `=` `1` ` ` `# Add remaining elements of b[]` ` ` `while` `j < n:` ` ` `sum2 ` `+` `=` `ar2[j]` ` ` `j ` `+` `=` `1` ` ` `# Add maximum of two sums of remaining elements` ` ` `result ` `+` `=` `max` `(sum1, sum2)` ` ` `return` `result` `# Driver code` `ar1 ` `=` `[` `2` `, ` `3` `, ` `7` `, ` `10` `, ` `12` `, ` `15` `, ` `30` `, ` `34` `]` `ar2 ` `=` `[` `1` `, ` `5` `, ` `7` `, ` `8` `, ` `10` `, ` `15` `, ` `16` `, ` `19` `]` `m ` `=` `len` `(ar1)` `n ` `=` `len` `(ar2)` `# Function call` `print` `"Maximum sum path is"` `, maxPathSum(ar1, ar2, m, n)` `# This code is contributed by __Devesh Agrawal__` |

## C#

`// C# program for Maximum Sum Path in` `// Two Arrays` `using` `System;` `class` `GFG {` ` ` `// Utility function to find maximum` ` ` `// of two integers` ` ` `static` `int` `max(` `int` `x, ` `int` `y) { ` `return` `(x > y) ? x : y; }` ` ` `// This function returns the sum of` ` ` `// elements on maximum path from` ` ` `// beginning to end` ` ` `static` `int` `maxPathSum(` `int` `[] ar1, ` `int` `[] ar2, ` `int` `m,` ` ` `int` `n)` ` ` `{` ` ` `// initialize indexes for ar1[]` ` ` `// and ar2[]` ` ` `int` `i = 0, j = 0;` ` ` `// Initialize result and current` ` ` `// sum through ar1[] and ar2[].` ` ` `int` `result = 0, sum1 = 0, sum2 = 0;` ` ` `// Below 3 loops are similar to` ` ` `// merge in merge sort` ` ` `while` `(i < m && j < n) {` ` ` `// Add elements of ar1[] to sum1` ` ` `if` `(ar1[i] < ar2[j])` ` ` `sum1 += ar1[i++];` ` ` `// Add elements of ar2[] to sum2` ` ` `else` `if` `(ar1[i] > ar2[j])` ` ` `sum2 += ar2[j++];` ` ` `// we reached a common point` ` ` `else` `{` ` ` `// Take the maximum of two sums and add to` ` ` `// result` ` ` `// Also add the common element of array,` ` ` `// once` ` ` `result += max(sum1, sum2) + ar1[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 of ar1[]` ` ` `while` `(i < m)` ` ` `sum1 += ar1[i++];` ` ` `// Add remaining elements of ar2[]` ` ` `while` `(j < n)` ` ` `sum2 += ar2[j++];` ` ` `// Add maximum of two sums of` ` ` `// remaining elements` ` ` `result += max(sum1, sum2);` ` ` `return` `result;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `[] ar1 = { 2, 3, 7, 10, 12, 15, 30, 34 };` ` ` `int` `[] ar2 = { 1, 5, 7, 8, 10, 15, 16, 19 };` ` ` `int` `m = ar1.Length;` ` ` `int` `n = ar2.Length;` ` ` `// Function call` ` ` `Console.Write(` `"Maximum sum path is :"` ` ` `+ maxPathSum(ar1, ar2, m, n));` ` ` `}` `}` `// This code is contributed by nitin mittal.` |

## PHP

`<?php` `// PHP Program to find Maximum Sum` `// Path in Two Arrays` `// This function returns the sum of` `// elements on maximum path` `// from beginning to end` `function` `maxPathSum(` `$ar1` `, ` `$ar2` `, ` `$m` `, ` `$n` `)` `{` ` ` ` ` `// initialize indexes for` ` ` `// ar1[] and ar2[]` ` ` `$i` `= 0;` ` ` `$j` `= 0;` ` ` `// Initialize result and` ` ` `// current sum through ar1[]` ` ` `// and ar2[].` ` ` `$result` `= 0;` ` ` `$sum1` `= 0;` ` ` `$sum2` `= 0;` ` ` `// Below 3 loops are similar` ` ` `// to merge in merge sort` ` ` `while` `(` `$i` `< ` `$m` `and` `$j` `< ` `$n` `)` ` ` `{` ` ` ` ` `// Add elements of` ` ` `// ar1[] to sum1` ` ` `if` `(` `$ar1` `[` `$i` `] < ` `$ar2` `[` `$j` `])` ` ` `$sum1` `+= ` `$ar1` `[` `$i` `++];` ` ` `// Add elements of` ` ` `// ar2[] to sum2` ` ` `else` `if` `(` `$ar1` `[` `$i` `] > ` `$ar2` `[` `$j` `])` ` ` `$sum2` `+= ` `$ar2` `[` `$j` `++];` ` ` `// we reached a` ` ` `// common point` ` ` `else` ` ` `{` ` ` ` ` `// Take the maximum of two sums and add to` ` ` `// result` ` ` `//Also add the common element of array, once` ` ` `$result` `+= max(` `$sum1` `, ` `$sum2` `) + ` `$ar1` `[` `$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 of ar1[]` ` ` `while` `(` `$i` `< ` `$m` `)` ` ` `$sum1` `+= ` `$ar1` `[` `$i` `++];` ` ` `// Add remaining elements of ar2[]` ` ` `while` `(` `$j` `< ` `$n` `)` ` ` `$sum2` `+= ` `$ar2` `[` `$j` `++];` ` ` `// Add maximum of two sums` ` ` `// of remaining elements` ` ` `$result` `+= max(` `$sum1` `, ` `$sum2` `);` ` ` `return` `$result` `;` `}` ` ` `// Driver Code` ` ` `$ar1` `= ` `array` `(2, 3, 7, 10, 12, 15, 30, 34);` ` ` `$ar2` `= ` `array` `(1, 5, 7, 8, 10, 15, 16, 19);` ` ` `$m` `= ` `count` `(` `$ar1` `);` ` ` `$n` `= ` `count` `(` `$ar2` `);` ` ` `// Function call` ` ` `echo` `"Maximum sum path is "` ` ` `, maxPathSum(` `$ar1` `, ` `$ar2` `, ` `$m` `, ` `$n` `);` ` ` `// This code is contributed by anuj_67.` `?>` |

## Javascript

`<script>` `// Javasvript program to find maximum sum path` `// Utility function to find maximum of two integers` `function` `max(x, y)` `{` ` ` `return` `(x > y) ? x : y;` `}` `// This function returns the sum of elements` `// on maximum path from beginning to end` `function` `maxPathSum(ar1, ar2, m, n)` `{` ` ` ` ` `// Initialize indexes for ar1[] and ar2[]` ` ` `let i = 0, j = 0;` ` ` `// Initialize result and current sum` ` ` `// through ar1[] and ar2[].` ` ` `let result = 0, sum1 = 0, sum2 = 0;` ` ` `// Below3 loops are similar to` ` ` `// merge in merge sort` ` ` `while` `(i < m && j < n)` ` ` `{` ` ` ` ` `// Add elements of ar1[] to sum1` ` ` `if` `(ar1[i] < ar2[j])` ` ` `sum1 += ar1[i++];` ` ` `// Add elements of ar2[] to sum2` ` ` `else` `if` `(ar1[i] > ar2[j])` ` ` `sum2 += ar2[j++];` ` ` ` ` `// We reached a common point` ` ` `else` ` ` `{` ` ` `// Take the maximum of two sums and add to` ` ` `// result` ` ` `//Also add the common element of array, once` ` ` `result += Math.max(sum1, sum2) + ar1[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 of ar1[]` ` ` `while` `(i < m)` ` ` `sum1 += ar1[i++];` ` ` `// Add remaining elements of ar2[]` ` ` `while` `(j < n)` ` ` `sum2 += ar2[j++];` ` ` `// Add maximum of two sums of` ` ` `// remaining elements` ` ` `result += Math.max(sum1, sum2);` ` ` `return` `result;` `}` `// Driver code` `let ar1 = [ 2, 3, 7, 10, 12, 15, 30, 34 ];` `let ar2 = [ 1, 5, 7, 8, 10, 15, 16, 19 ];` `let m = ar1.length;` `let n = ar2.length;` `// Function call` `document.write(` `"Maximum sum path is "` `+` ` ` `maxPathSum(ar1, ar2, m, n));` ` ` `// This code is contributed by Mayank Tyagi` `</script>` |

**Output**

Maximum sum path is 122

__Complexity Analysis__:

**Space Complexity:**O(1).

Any extra space is not required, so the space complexity is constant.**Time complexity:**O(m+n).

In every iteration of while loops, an element from either of the two arrays is processed. There are total m + n elements. Therefore, the time complexity is O(m+n).

This article is contributed by **Piyush Gupta**. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.