Last Updated: 29 Mar, 2021

Maximize Sum

Easy

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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-

Initialise a 2-D ‘dp’ list (array) for keeping track of the maximised sums calculated for each element ‘i’.
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).
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]))
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.

Solve now