Maximize Sum

Easy
0/40
Average time to solve is 15m
153 upvotes
Asked in companies
SamsungVisaNagarro Software

Problem statement

You are given two arrays of the same size. Your task is to maximize the possible sum that can be calculated using elements of the two given arrays. You are allowed to swap elements between the arrays at the same position any number of times to achieve this.

Note: 
The maximum sum is calculated by using the following rules:-

For every ‘i’ in range 0...N:

Max_sum += abs(arr1[i] - arr2[i])

And If i < N-1:
    Max_sum += abs(arr1[i+1] - arr2[i])
For Example 
Input:
n = 4
arr1[] = {2,3,4,1}
arr2[] = {2,4,1,1}

Ouput: 11


Explanation:

Here we will swap arr1[2] and arr2[2]. (Swap)

arr1[] = {2,3,1,1}
arr2[] = {2,4,4,1}

for this type of arrangement, we have our maximum Define Sum.

Sum = abs(arr1[0]-arr2[0]) + abs(arr1[1]-arr2[0]) + abs(arr1[1]-arr2[1]) + abs(arr1[2]-arr2[1]) ....
Sum = abs(2-2) + abs(3-2) + abs(3-4) + abs(1-4) + abs(1-4) + abs(1-4) + abs(1-1) = 11
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains a single integer ‘T’ denoting the number of test cases that would be there.

The first line of each test case contains a single integer ‘N’ denoting the number of integers that would be given in both the lists (arrays).

The next two lines contain ‘N’ space-separated integers denoting the elements of the two lists which would be given.
Output Format : 
Return maximised possible sum which can be calculated using the elements of the two given lists as depicted by the formula mentioned above.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
1 <= nums[i] <= 10^6


Time Limit: 1sec
Sample Input 1 :
2
4
2 2 4 3
2 4 2 3
5
5 5 6 6 5
1 2 5 4 3
Sample Output 1 :
9
24

Explanation for Sample 1 :

Here we will swap arr1[2] and arr2[2]. (Swap)

arr1[] = {2,4,4,3}
arr2[] = {2,2,2,3}

for this type of arrangement, we have our maximum Define Sum.

Sum = abs(arr1[0]-arr2[0]) + abs(arr1[1]-arr2[0]) + abs(arr1[1]-arr2[1]) + abs(arr1[2]-arr2[1]) ....
Sum = abs(2-2) + abs(4-2) + abs(4-2) + abs(4-2) + abs(4-2) + abs(3-2) + abs(3-3) = 9



Here we will swap arr1[3] and arr2[3] and Also swap arr1[4] and arr2[4]. (Swap)

arr1[] = {5,5,6,4,3}
arr2[] = {1,2,5,6,5}

for this type of arrangement, we have our maximum Defined Sum.

Sum = abs(arr1[0]-arr2[0]) + abs(arr1[1]-arr2[0]) + abs(arr1[1]-arr2[1]) + abs(arr1[2]-arr2[1]) ....
Sum = abs(5-1) + abs(5-1) + abs(5-2) + abs(6-2) + abs(6-5) + abs(6-5) + abs(4-6) + abs(3-6) + abs(3-5) = 24
Sample Input 2 :
1
4
2 3 4 1
2 4 1 1
Sample Output 2 :
11
Hint

Try to find a pattern of solving repeated sub-problems and use dynamic programming to solve them.

Approaches (1)
Maximize Sum

The idea here is to maximise the sum possible by choosing whether to swap the list elements between the two given lists (arrays) or not. if the array elements are swapped and the sum is maximised, then we perform swapping otherwise we calculate the maximum sum for the ‘i’th element without any swapping and move on to calculating the sum for the remaining elements.

The algorithm will be-

  1. Initialise a 2-D ‘dp’ list (array) for keeping track of the maximised sums calculated for each element ‘i’.
  2. For each array element ‘i’, dp[i][0] would keep track of the maximised sum possible without swapping the ‘i’th elements between the two lists (arrays) while dp[i][1] would keep track of the maximised sum possible after swapping the ‘i’th elements of the lists (arrays).
  3. In every iteration the dp[i][0] and dp[i][1] can be calculated in the following manner:-
    1. dp[i][0] = abs(arr1[i] - arr2[i]) + max(dp[i-1][0] + abs(arr1[i] - arr2[i-1]), dp[i-1][1] + abs(arr1[i] - arr1[i-1]))
    2. dp[i][1] = abs(arr1[i] - arr2[i]) + max(dp[i-1][0] + abs(arr2[i] - arr2[i-1]), dp[i-1][1] + abs(arr2[i] - arr1[i-1]))
  4. After each iteration we store the maximum between the dp[i][0] and dp[i][1] that we have calculated in each step and keep adding it to return our final calculated maximum sum.
Time Complexity

O(N), 

where ‘N’ denotes the number of items given in the problem for the two lists.

Since we are iterating through all the elements in the problem therefore, the time complexity will be O(N).

Space Complexity

O(N), 

where ‘N’ denotes the number of items given in the problem.

We iterate through the list (array) and construct a 2D list (array) ‘dp’ of elements and count O(N). That is why the space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximize Sum
Full screen
Console