{"id":1240,"date":"2020-06-10T17:13:41","date_gmt":"2020-06-10T17:13:41","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1240"},"modified":"2022-06-17T06:15:21","modified_gmt":"2022-06-17T06:15:21","slug":"maximum-sum-rupees","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximum-sum-rupees\/","title":{"rendered":"Maximum Sum Rupees"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

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.<\/p>\n<\/blockquote>\n

Test Case<\/h4>\n
Input:\n1\n5 4\n3 2 12 10 7\n8 7 5 1 \n\nOutput:\n35\n\nExplanation:\nThe maximum sum will be 1+5+7+10+12=35.<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n
Solving Approach :<\/h3>\n
\n
1) We can sort both arrays here and maintain two sum values to keep the sum from both arrays.
\n2) 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.
\n3) 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.
\nFinal sum saved would be our answer.<\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
Let both arrays be,<\/p>\n
\"\"<\/p>\n
Sorting both of them lets us count in a efficient way, so after sorting both arrays becomes,<\/p>\n
\"\"
\nWe maintain 3 variables,<\/p>\n
sumA<\/code> for sum from array A<\/code><\/p>\n
sumB<\/code> for sum from array B<\/code><\/p>\n
finalSum<\/code> for final sum to be printed<\/p>\n
Now, we traverse until a common element is found and add traversed elements in sum variables of respective array,<\/p>\n
\"\"<\/p>\n
sumA<\/code> = 2 + 3 + 7<\/code> => 12<\/p>\n
sumB<\/code> = 1 + 5 + 7<\/code> => 13<\/p>\n
We add the maximum sum value from both arrays in our finalSum<\/code> variable, and set sumA<\/code>, sumB<\/code> to 0.<\/p>\n
finalSum<\/code> = finalSum<\/code> + (sumA,sumB)<\/code><\/p>\n
finalSum<\/code> = 0 + max(12,13)<\/code><\/p>\n
finalSum<\/code> = 0 + 13<\/p>\n
finalSum<\/code> = 13<\/p>\n
Now, we repeat the same procedure until we encounter common elements or arrays are traversed completely,<\/p>\n
\"\"<\/p>\n
sumA<\/code> = 10 + 12<\/code> => 22<\/p>\n
sumB<\/code> = 8<\/code> => 8<\/p>\n
Hence, we save maximum of both in finalSum<\/code>,<\/p>\n
finalSum<\/code> = finalSum<\/code> + (sumA,sumB)<\/code><\/p>\n
finalSum<\/code> = 13 + max(22,8)<\/code><\/p>\n
finalSum<\/code> = 13 + 22<\/p>\n
finalSum<\/code> = 35<\/p>\n
As, both arrays are traversed, finalSum<\/code> is our answer and we print it.<\/p>\n<\/blockquote>\n
Solutions<\/h3>\n
\t\t\t\t\t\t