Maximize the sum

In this problem, our primary focus is on the common elements i.e. an element that is present in both the arrays. Then, we have to decide whether we have to make a switch. So for that, first we store all the elements of ‘ARR1’ and ‘ARR2’ into ‘MAP1’ and ‘MAP2’ respectively. 

Now we call our ‘maximiseSumHelper’ function. We call this function for both cases i.e starting with ‘ARR1’ and starting with ‘ARR2’. Then we return the maximum of the two cases. During the recursive call, if we find a common element that is present in both the arrays, then we have two options at that point i.e. either we can switch to the other array or ontinue with the same array.

Here is the algorithm :

• We declare two HashMaps i.e. ‘MAP1’ and ‘MAP2’ in which we store elements of ‘ARR1’ and ‘ARR2’ respectively.
• Return max(maximiseSumHelper(‘ARR1’, ‘ARR2’, 1, 0),maximiseSumHelper(‘ARR1’, ‘ARR2’, 2, 0))

maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’) function works as follows:

• Base Case:
  • If the ‘currInd’ is greater than or equal to the current array's size, we have reached the end of the array. So we return 0. 
• We declare a variable ‘maximumSum’ in which we store our answer.
• If ‘currArr’ == 1:
  • ‘maximumSum’ = ‘ARR1[‘currInd’]’ + maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’ + 1)
  • If ‘ARR1[currInd]’ is present in both the arrays:
    • Now we take both the cases i.e. we can either switch from the current array to the other array or we will continue with the same array.
• Else
  • ‘maximumSum’ = ‘ARR2[‘currInd’]’ + ‘maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’ + 1)
  • If ‘ARR2[currInd]’ is present in both the arrays:
    • Again, we take both cases i.e. we can switch from the current array to the other array or we will continue with the same array.
• Finally, return ‘maximumSum’.

In our previous approach, we use a recursive solution for solving this problem. But there are a lot of repetitive calculations in our previous approach. Let's assume a case in which both the arrays contain the same values, say ‘ARR1’ = [1, 2, 3, 4] and ‘ARR2’ = [1, 2, 3, 4].

So in this case at every index, we have two choices i.e either we can switch to the other array or we can continue with the same array. So here we can use memoization to get rid of repetitive calls.

Here is the algorithm :

This approach is similar to the previous approach with some additions. In this approach, we use the ‘memo’ array. 

Here ‘memo[0][j]’ stores the maximum sum till now when ‘ARR1’ has ‘i’ elements.

And ‘memo[1][j]’ stores the maximum sum till now when ‘ARR2’ has ‘j’ elements.

maximiseSumHelper(‘ARR1’, ‘ARR2’, ‘currArr’, ‘currInd’, ’memo’) function is the same as described in the previous approach with some additions: 

• If we already have calculated the result for ‘memo[i][j]’ i.e. ‘memo[‘currArr’][‘currInd’]’ != -1’
  • Return memo[‘currArr’][‘currInd’]’ .
• We declare a variable ‘maximumSum’ in which we store our answer.
• If ‘currArr’ == 1
  • We calculate ‘maximumSum’  as stated in the previous approach as set ‘memo[0][currInd]’ = ‘maximumSum’ .
• Else:
  • We calculate ‘maximumSum’  as stated in the previous approach as set ‘memo[1][currInd]’ = ‘maximumSum’.

In this problem, our primary focus is on the common elements, i.e., elements present in both the arrays. Then, we have to decide whether we have to make a switch. So for that, we take two variables‘ currSumArr1’ and ‘currSumArr2’ in which we store the sum of all the elements between the current common element and the last common element of ‘ARR1’ and ‘ARR2’, respectively. And when we encounter a common element, we compare the accumulated sum in both paths, and we pick the bigger one. Then add this into ‘maximumSum.’

Here is the algorithm :

• We declare two variables, ‘i’ and ‘j,’ in which we store the current index of ‘ARR1’ and ‘ARR2’, respectively, and declare a ‘maximumSum’ in which we store our answer.
• We declare two variables, ‘currSumArr1’ and ‘currSumArr2’, in which we store the sum of all the elements between the current common element and the last common element of ‘ARR1’ and ‘ARR2’, respectively.
• We run a loop while ‘i’ < ‘ARR1.Length’ and ‘j’ < ‘ARR2.Length’:
  • If ‘ARR1[i]' < ‘ARR2[j]’:
    • ‘currSumArr1’ += ‘ARR1[i]’
    • ‘i++’
  • Else if ‘ARR1[i]' > ‘ARR2[j]’:
    • ‘currSumArr2’ += ‘ARR2[j]’
    • ‘J++’
  • Else, when we get the common element, we add the maximum of ‘currSumArr1’ and ’currSumArr2’ to our resultant answer:
    • ‘maximumSum’ += max(‘currSumArr1’,’currSumArr2’)
    • ‘maximumSum’ += ‘ARR1[i]’
    • ‘currSumArr1’ = 0 , ‘currSumArr2’ = 0
    • ‘i’ += 1
    • ‘j’ += 1
• We run a loop while ‘i’ < ‘ARR1.Length’:
  • ‘currSumArr1’ += ‘ARR1[i]’
  • ‘i++’
• We run a loop while ‘j’ < ‘ARR2.Length’
  • ‘currSumArr2’ += ‘ARR2[j]’
  • ‘j++’
• ‘maximumSum’ += max(‘currSumArr1’,’currSumArr2’).
• Finally, we return ‘maximumSum’.