Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach(Dynamic Programming)
2.1.
Steps of Algorithm:
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024

Maximize the sum of the product of two arrays at corresponding indexes by reversing at most one subarray of the first array

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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:

  1. Create a 2D array dp[N][N].
  2. Make One Variable maximumSum, which will initially store the sum of A[i]*B[i], when no subarray is reversed. 
  3.  Initialize Dp array for subarray of length 1 and 2. 
  4. Now we will iterate the complete Dp array and fill the value of Dp[L][R] as explained above.
  5. Now again, traverse the Dp array to find the maximum possible value and store it in the maximumSum variable.

 

Implementation in C++

// c++ code for finding the maximum sum of the product 
#include<bits/stdc++.h>
using namespace std;
int maxProSum(int *A,int *B, int N){
    // initializing Dp array
    int Dp[N][N];
    
    // We will store the maximum sum of the product 
    int maximumSum = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            Dp[i][j] = 0;
        }
    }
    
    // Finding the sum when no subarray is reversed
    for(int i=0;i<N;i++){
        maximumSum += A[i]*B[i];
    }

    // initializing the Dp array for subarray of length 1 and 2
    for(int i=0;i<N;i++){
        // initializing only those where both L and R are same
        // like 1 1, 2 2, 3 3 and so on
        Dp[i][i] = maximumSum;
        
        // initializing for the length 2
        if(i<N-1){
            int L = i;
            int R = i+1;
            Dp[L][R] = maximumSum + (A[L]*B[R]) + (A[R]*B[L]) - (A[L]*B[L]) - (A[R]*B[R]);
        }
    }
    
    for(int R=0;R<N;R++){
        for(int L=0;L<N;L++){
            // calculating the complete Dp array.
            if(R-L+1>2){
                Dp[L][R] = Dp[L+1][R-1] + (A[L]*B[R]) + (A[R]*B[L]) - (A[L]*B[L]) - (A[R]*B[R]);
            }
        }
    }

    // finding the maximum sum from the Dp array
    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++){
            maximumSum = max(maximumSum, Dp[i][j]);
        }
    }
    return maximumSum;
}
int main(){
    int A[] = {1,5,2,3};
    int B[] = {1,4,3,2};
    cout << maxProSum(A,B,4) << endl;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output: 

34

 

Complexity Analysis

Time Complexity: O(N^2)

Explanation: Since we traverse rows and columns of size N, the time complexity is O(N^2).

Space Complexity: O(N^2)

Explanation: We are storing the answer for each row and column in the Dp array of NxN size; therefore, space complexity is O(N^2). 

Must Read  C Program to Reverse a Number

Frequently asked questions

Q1. What is Dynamic Programming Approach? 

Ans. Dynamic programming is an approach to optimize recursive solutions when recursive calls on the same input repeatedly. The idea is simple, store the result and need to calculate again and again to use it.  

 

Q2. Which sorting algorithm is used when we sort using STL? 

Ans. The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.

 

Q3. What is the greedy approach? 

Ans. It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution. 

Key takeaways

In this article, we have discussed the problem of maximizing the sum of the product of two arrays at corresponding indexes by reversing at most one subarray of the first array. We discussed the Dp-based optimized solution. We hope you understand the problem and solution properly. Now you can also easily attempt the sum of two arrays problem.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Live masterclass