Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Maximum Sum Rupees

Last Updated on June 17, 2022 by Ria Pathak

Sorting

Hard

### Problem Statement (Simplified):

We have to find the maximum sum of elements from two arrays, such that you can select elements to add only from one array. You can switch array only at index where both indexes have the same elements.

#### Test Case

``````Input:
1
5 4
3 2 12 10 7
8 7 5 1

Output:
35

Explanation:
The maximum sum will be 1+5+7+10+12=35.``````

See original problem statement here

### Solving Approach :

1) We can sort both arrays here and maintain two sum values to keep the sum from both arrays.
2) As we can switch from one array to another only at indices containing the same elements, we can calculate sum up to the common element and save the larger one into our final sum.
3) We’ll calculate the sum of array elements in the respective sum variable until there comes an element that is common in both, we compare both sum variables and saves the maximum of both in our final sum. We repeat this until we get the end of arrays.
Final sum saved would be our answer.

### Example

Let both arrays be,

Sorting both of them lets us count in a efficient way, so after sorting both arrays becomes,

We maintain 3 variables,

`sumA` for sum from array `A`

`sumB` for sum from array `B`

`finalSum` for final sum to be printed

Now, we traverse until a common element is found and add traversed elements in sum variables of respective array,

`sumA` = `2 + 3 + 7` => 12

`sumB` = `1 + 5 + 7` => 13

We add the maximum sum value from both arrays in our `finalSum` variable, and set `sumA`, `sumB` to 0.

`finalSum` = `finalSum` + `(sumA,sumB)`

`finalSum` = 0 + `max(12,13)`

`finalSum` = 0 + 13

`finalSum` = 13

Now, we repeat the same procedure until we encounter common elements or arrays are traversed completely,

`sumA` = `10 + 12` => 22

`sumB` = `8` => 8

Hence, we save maximum of both in `finalSum`,

`finalSum` = `finalSum` + `(sumA,sumB)`

`finalSum` = 13 + `max(22,8)`

`finalSum` = 13 + 22

`finalSum` = 35

As, both arrays are traversed, `finalSum` is our answer and we print it.

### Solutions

```#include <stdio.h>

void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main()
{

int test;
scanf("%d",&test);

while(test--){

int m, n;
scanf("%d%d",&m,&n);

int a[m], b[n];
for(int i=0; i<m; i++)
scanf("%d",&a[i]);
mergeSort(a,0,m-1);

for(int i=0; i<n; i++)
scanf("%d",&b[i]);
mergeSort(b,0,n-1);

int i=0, j=0;

int finalSum=0,sumA=0, sumB=0;

while(i<m && j<n)
{
if (a[i]<b[j])
sumA += a[i++];
else if (a[i]>b[j])
sumB += b[j++];

else{
finalSum += (sumA>sumB)?sumA:sumB;
sumA = 0, sumB = 0;
while(i<m && j<n && a[i]==b[j]){
finalSum +=  a[i++];
j++;
}
}
}

while (i<m)
sumA+=a[i++];
while (j<n)
sumB+=b[j++];

finalSum+=(sumA>sumB)?sumA:sumB;
printf("%d\n",finalSum);
}

}
```
```#include <bits/stdc++.h>
using namespace std;

void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main()
{

int test;
cin>>test;

while(test--){

int m, n;
cin>>m>>n;

int a[m], b[n];
for(int i=0; i<m; i++)
cin>>a[i];
mergeSort(a,0,m-1);

for(int i=0; i<n; i++)
cin>>b[i];
mergeSort(b,0,n-1);

int i=0, j=0;

int finalSum=0,sumA=0, sumB=0;

while(i<m && j<n)
{
if (a[i]<b[j])
sumA += a[i++];
else if (a[i]>b[j])
sumB += b[j++];

else{
finalSum += max(sumA, sumB);
sumA = 0, sumB = 0;
while(i<m && j<n && a[i]==b[j]){
finalSum +=  a[i++];
j++;
}
}
}

while (i<m)
sumA+=a[i++];
while (j<n)
sumB+=b[j++];

finalSum+=max(sumA, sumB);
cout<<finalSum<<endl;
}

}
```
```import java.util.*;
import java.io.*;

public class Main {

static void merge(int arr[], int start, int mid, int end){
int left[] = new int[mid-start+1];
int right[] = new int[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

static void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int test = sc.nextInt();

while(test--!=0){

int m = sc.nextInt(), n = sc.nextInt();

int a[] = new int[m], b[] = new int[n];
for(int i=0; i<m; i++)
a[i] = sc.nextInt();
mergeSort(a,0,m-1);

for(int i=0; i<n; i++)
b[i] = sc.nextInt();
mergeSort(b,0,n-1);

int i=0, j=0;

int finalSum=0,sumA=0, sumB=0;

while(i<m && j<n)
{
if (a[i]<b[j])
sumA += a[i++];
else if (a[i]>b[j])
sumB += b[j++];

else{
finalSum += (sumA>sumB)?sumA:sumB;
sumA = 0;
sumB = 0;
while(i<m && j<n && a[i]==b[j]){
finalSum +=  a[i++];
j++;
}
}
}

while (i<m)
sumA+=a[i++];
while (j<n)
sumB+=b[j++];

finalSum+=(sumA>sumB)?sumA:sumB;
System.out.println(finalSum);
}

}
}
```
```def merge(arr, start, mid, end):
left = [0 for i in range(mid - start + 1)]
right = [0 for i in range(end - mid)]

for i in range(start, mid + 1):
left[i - start] =  arr[i]

for i in range(mid + 1, end + 1):
right[i - (mid + 1)] = arr[i]

leftIndex = 0
rightIndex = 0
arrIndex = start

while leftIndex <= mid - start and rightIndex < end - mid:

if(left[leftIndex] < right[rightIndex]):
arr[arrIndex] = left[leftIndex]
leftIndex += 1

else:
arr[arrIndex] = right[rightIndex]
rightIndex += 1

arrIndex += 1

while(leftIndex <= mid - start):
arr[arrIndex] = left[leftIndex]
leftIndex += 1
arrIndex += 1

while(rightIndex < end - mid):
arr[arrIndex] = right[rightIndex]
rightIndex += 1
arrIndex += 1

def mergeSort(arr, start, end):
if(end == start):
return
mergeSort(arr, start, (start + end) // 2)
mergeSort(arr, ((start + end) // 2) + 1, end)
merge(arr, start, (start + end) // 2, end)

for _ in range(int(input())):

m, n = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mergeSort(a, 0, m - 1)
mergeSort(b, 0, n - 1)
i, j = 0, 0
finalSum, sumA, sumB = 0, 0, 0

while(i < m and j < n):

if (a[i] < b[j]):
sumA += a[i]
i += 1

elif (a[i] > b[j]):
sumB += b[j]
j += 1

else:
finalSum += max(sumA, sumB)
sumA = 0
sumB = 0
while(i < m and j<n and a[i]==b[j]):
finalSum +=  a[i]
i += 1
j += 1

while (i<m):
sumA += a[i]
i += 1

while (j<n):
sumB += b[j]
j += 1

finalSum += max(sumA, sumB)
print(finalSum)
```

[forminator_quiz id="1242"]

### Space Complexity

O(`1`)

This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.