Introduction
Problem Statement
The problem states we are given two arrays, let say A[] and B[]. We need to maximize the sum of the product of A[i]*B[i] for every i(0<=i<n) where n is the size of the array. We are allowed to reverse at most one subarray in array A[]. We need to print the maximum sum achievable by doing the above operation.
We will discuss the Dp-based approach, along with sample examples and c++ code.
Sample Examples
Example 1:
Input:
N = 4
A[] = {1,5,2,3}
B[] = {1,4,3,2}
Output: 34
Explanation:
We will reverse the [2,3] in array A, then array will look like A[] = {1,5,3,2}. Now the sum of A[i]*B[i] = 1*1 + 5*4 + 3*3 + 2*2 = 34 which is maximum sum of the product.
Example 2:
Input:
N = 4
A[] = {6,7,3}
B[] = {5,1,7}
Output: 82
Explanation:
We will reverse the [1,2] in array A, then array will look like A[] = {6,3,7}. Now the sum of A[i]*B[i] = 6*5 + 7*1 + 3*7 = 82 which is maximum sum of the product.
Approach(Dynamic Programming)
The idea is to use the dynamic programming approach. We will create a 2D Dp[][] array, say dp[][], where dp[L][R] will represent the sum of the product A[i] and B[i], after reversing the array A[] in the range [L, R]. Now, if array A is reversed in the range [L, R], it means it is reversed in the range [L+1, R-1] also. So we will use this fact to calculate dp[L][R] from Dp[L+1][R-1].
If we look closely we can notice that Dp[L][R] = Dp[L+1][R-1] + (A[L]*B[R]) + (A[R]*B[L]) - A[L]*B[L] - A[R]*B[R] because when we have calculated Dp[L+1][R-1], A[R]*B[R] and A[L]*B[L] was added, and to calculate Dp[L][R], A[L]*B[R] and B[L]*A[R] needs to be added. So we have subtracted A[R]*B[R] , A[L]*B[L] and added A[L]*B[R], B[L]*A[R]. After calculating Dp[L][R] for every range, print the maximum possible answer.
Now the logic should be clear. Now let’s implement the above logic into the C++ code.
Steps of Algorithm:
- Create a 2D array dp[N][N].
- Make One Variable maximumSum, which will initially store the sum of A[i]*B[i], when no subarray is reversed.
- Initialize Dp array for subarray of length 1 and 2.
- Now we will iterate the complete Dp array and fill the value of Dp[L][R] as explained above.
- Now again, traverse the Dp array to find the maximum possible value and store it in the maximumSum variable.