Given two arrays A and B of size N, the task is to maximize the sum of A[i]*B[i] across all values of i from 0 to N-1 by reversing at most one subarray of array A.
Examples:
Input: N = 4, A = [5, 1, 2, 3], B = [1, 4, 3, 2]
Output: 33
Explanation: Array A after reversing the subarray A[0, 1] will become [1, 5, 2, 3]. Sum of A[i]*B[i] after the reversal becomes 1*1+5*4+2*3+3*2 = 33.Input: N = 3, A = [6, 7, 3], B = [5, 1, 7]
Output: 82
Naive Approach: One simple way to solve this problem is to check for all possible subarrays of A and reverse them one by one to find the maximum possible value of the sum.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of A[i]*B[i]// across all values of i from 0 to N-1 by reversing// at most one subarray of array Aint maxSum(vector<int>& A, vector<int>& B){ int N = A.size(); // Initialising maximum possible sum variable int maxPosSum = 0; // Iterating for all subarrays for (int L = 0; L < N - 1; L++) { for (int R = L; R < N; R++) { // Variable for storing the sum after reversing // The subarray from L to R int curSum = 0; for (int i = 0; i < N; i++) { // Checking if the current index is in the // reversed subarray if (i >= L && i <= R) curSum += A[L + R - i] * B[i]; else curSum += A[i] * B[i]; } // Updating the answer maxPosSum = max(maxPosSum, curSum); } } // Returning the Maximum Possible Sum of product return maxPosSum;}// Driver Codeint main(){ // Given Input int N = 4; vector<int> A = { 5, 1, 2, 3 }, B = { 1, 4, 3, 2 }; cout << maxSum(A, B);} |
Java
// Java code to implement above approachimport java.util.*;public class GFG { // Function to find the maximum sum of A[i]*B[i] // across all values of i from 0 to N-1 by reversing // at most one subarray of array A static int maxSum(int []A, int []B) { int N = A.length; // Initialising maximum possible sum variable int maxPosSum = 0; // Iterating for all subarrays for (int L = 0; L < N - 1; L++) { for (int R = L; R < N; R++) { // Variable for storing the sum after reversing // The subarray from L to R int curSum = 0; for (int i = 0; i < N; i++) { // Checking if the current index is in the // reversed subarray if (i >= L && i <= R) curSum += A[L + R - i] * B[i]; else curSum += A[i] * B[i]; } // Updating the answer maxPosSum = Math.max(maxPosSum, curSum); } } // Returning the Maximum Possible Sum of product return maxPosSum; } // Driver code public static void main(String args[]) { // Given Input int N = 4; int []A = { 5, 1, 2, 3 }; int []B = { 1, 4, 3, 2 }; System.out.println(maxSum(A, B)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach# Function to find the maximum sum of A[i]*B[i]# across all values of i from 0 to N-1 by reversing# at most one subarray of array Adef maxSum(A, B): N = len(A) # Initialising maximum possible sum variable maxPosSum = 0 # Iterating for all subarrays for L in range(N - 1): for R in range(L, N): # Variable for storing the sum after reversing # The subarray from L to R curSum = 0 for i in range(N): # Checking if the current index is in the # reversed subarray if (i >= L and i <= R): curSum += A[L + R - i] * B[i] else: curSum += A[i] * B[i] # Updating the answer maxPosSum = max(maxPosSum, curSum) # Returning the Maximum Possible Sum of product return maxPosSum# Driver Code# Given InputN = 4A = [5, 1, 2, 3]B = [1, 4, 3, 2]print(maxSum(A, B))# This code is contributed by gfgking |
C#
// C# code to implement above approachusing System;public class GFG { // Function to find the maximum sum of A[i]*B[i] // across all values of i from 0 to N-1 by reversing // at most one subarray of array A static int maxSum(int []A, int []B) { int N = A.Length; // Initialising maximum possible sum variable int maxPosSum = 0; // Iterating for all subarrays for (int L = 0; L < N - 1; L++) { for (int R = L; R < N; R++) { // Variable for storing the sum after reversing // The subarray from L to R int curSum = 0; for (int i = 0; i < N; i++) { // Checking if the current index is in the // reversed subarray if (i >= L && i <= R) curSum += A[L + R - i] * B[i]; else curSum += A[i] * B[i]; } // Updating the answer maxPosSum = Math.Max(maxPosSum, curSum); } } // Returning the Maximum Possible Sum of product return maxPosSum; } // Driver code public static void Main() { // Given Input int []A = { 5, 1, 2, 3 }; int []B = { 1, 4, 3, 2 }; Console.Write(maxSum(A, B)); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum sum of A[i]*B[i] // across all values of i from 0 to N-1 by reversing // at most one subarray of array A function maxSum(A, B) { let N = A.length; // Initialising maximum possible sum variable let maxPosSum = 0; // Iterating for all subarrays for (let L = 0; L < N - 1; L++) { for (let R = L; R < N; R++) { // Variable for storing the sum after reversing // The subarray from L to R let curSum = 0; for (let i = 0; i < N; i++) { // Checking if the current index is in the // reversed subarray if (i >= L && i <= R) curSum += A[L + R - i] * B[i]; else curSum += A[i] * B[i]; } // Updating the answer maxPosSum = Math.max(maxPosSum, curSum); } } // Returning the Maximum Possible Sum of product return maxPosSum; } // Driver Code // Given Input let N = 4; let A = [5, 1, 2, 3], B = [1, 4, 3, 2]; document.write(maxSum(A, B)); // This code is contributed by Potta Lokesh </script> |
Output
33
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above problem can be solved with the use of dynamic programming. Follow the below steps to solve this problem:
- Let dp[L][[R] represent the sum of the product of A[i] and B[i] after reversing subarray A[L, R].
- Observe that if the subarray A[L, R] is reversed, the subarray A[L+1, R-1] is also reversed. Therefore, dp[L][R] can be calculated by the use of dp[L+1][R-1] and by using the formula:
dp[L][R] = dp[L+1][R-1]+ (A[R] * B[L]) – (A[L] * B[L]) + (A[L] * B[R]) – (A[R] * B[R])
- Because In the calculation of dp[L+1][R-1], A[L]*B[L] and A[R]*B[R] is added whereas for the calculation dp[L][R], A[R]*B[L] and A[L]*B[R ]is added.
- Hence we need to subtract A[L]*B[L] and A[R]*B[R] and add A[R]*B[L] and A[L]*B[R] to dp[L+1][R-1] for calculation of dp[L][R].
- Print the answer according to the above observation.
Below is the implementation of the dynamic programming approach.
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of A[i]*B[i]// across all values of i from 0 to N-1 by reversing// at most one subarray of array Aint maxSum(vector<int>& A, vector<int>& B){ int N = A.size(); // Initialising maximum possible sum variable int maxPosSum = 0; int dp[N][N]; // Initialising the dp array memset(dp, 0, sizeof(dp)); // Value of maxPosSum when no subarray is reversed for (int i = 0; i < N; i++) maxPosSum += A[i] * B[i]; // Initialising dp for subarray of length 1 for (int i = 0; i < N; i++) dp[i][i] = maxPosSum; // Initialising dp for subarray of length 2 for (int i = 0; i < N - 1; i++) { int R = i + 1; int L = i; dp[L][R] = maxPosSum + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } // Calculating the complete dp array for (int R = 0; R < N; R++) { for (int L = 0; L < N; L++) { // If length of subarray is less 3, then // continuing if (R - L + 1 < 3) continue; dp[L][R] = dp[L + 1][R - 1] + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } } // Updating the maxPosSum variable for (int L = 0; L < N; L++) { for (int R = L; R < N; R++) { maxPosSum = max(maxPosSum, dp[L][R]); } } // Returning the maximum possible sum of product return maxPosSum;}// Driver Codeint main(){ // Given Input vector<int> A = { 5, 1, 2, 3 }, B = { 1, 4, 3, 2 }; cout << maxSum(A, B); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{// Function to find the maximum sum of A[i]*B[i]// across all values of i from 0 to N-1 by reversing// at most one subarray of array Astatic int maxSum(int[] A, int[] B){ int N = A.length; // Initialising maximum possible sum variable int maxPosSum = 0; int [][]dp = new int[N][N]; // Value of maxPosSum when no subarray is reversed for (int i = 0; i < N; i++) maxPosSum += A[i] * B[i]; // Initialising dp for subarray of length 1 for (int i = 0; i < N; i++) dp[i][i] = maxPosSum; // Initialising dp for subarray of length 2 for (int i = 0; i < N - 1; i++) { int R = i + 1; int L = i; dp[L][R] = maxPosSum + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } // Calculating the complete dp array for (int R = 0; R < N; R++) { for (int L = 0; L < N; L++) { // If length of subarray is less 3, then // continuing if (R - L + 1 < 3) continue; dp[L][R] = dp[L + 1][R - 1] + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } } // Updating the maxPosSum variable for (int L = 0; L < N; L++) { for (int R = L; R < N; R++) { maxPosSum = Math.max(maxPosSum, dp[L][R]); } } // Returning the maximum possible sum of product return maxPosSum;}// Driver Codepublic static void main(String[] args){ // Given Input int[] A = { 5, 1, 2, 3 }, B = { 1, 4, 3, 2 }; System.out.print(maxSum(A, B));}}// This code is contributed by 29AjayKumar |
Python
# Python implementation of the above approach# Function to find the maximum sum of A[i]*B[i]# across all values of i from 0 to N-1 by reversing# at most one subarray of array Adef maxSum(A, B): N = len(A) # Initialising maximum possible sum variable maxPosSum = 0 # Initialising the dp array dp = ([[0 for i in range(N)] for i in range(N)]) # Value of maxPosSum when no subarray is reversed for i in range(0, N): maxPosSum = maxPosSum + (A[i] * B[i]) # Initialising dp for subarray of length 1 for i in range(0, N): dp[i][i] = maxPosSum # Initialising dp for subarray of length 2 for i in range(0, N - 1): R = i + 1 L = i dp[L][R] = maxPosSum + (A[R] * B[L]) - \ (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]) # Calculating the complete dp array for R in range(0, N): for L in range(0, N): # If length of subarray is less 3, then # continuing if (R - L + 1 < 3): continue dp[L][R] = dp[L + 1][R - 1] + \ (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]) # Updating the maxPosSum variable for R in range(0, N): for L in range(0, N): maxPosSum = max(maxPosSum, dp[L][R]) # Returning the maximum possible sum of product return maxPosSum# Driver Code# Given InputA = [5, 1, 2, 3]B = [1, 4, 3, 2]print(maxSum(A, B))# This code is contributed by Samim Hossain Mondal. |
C#
// C# implementation of the above approachusing System;class GFG { // Function to find the maximum sum of A[i]*B[i] // across all values of i from 0 to N-1 by reversing // at most one subarray of array A static int maxSum(int[] A, int[] B) { int N = A.Length; // Initialising maximum possible sum variable int maxPosSum = 0; int[, ] dp = new int[N, N]; // Initialising the dp array // memset(dp, 0, sizeof(dp)); // Value of maxPosSum when no subarray is reversed for (int i = 0; i < N; i++) maxPosSum += A[i] * B[i]; // Initialising dp for subarray of length 1 for (int i = 0; i < N; i++) dp[i, i] = maxPosSum; // Initialising dp for subarray of length 2 for (int i = 0; i < N - 1; i++) { int R = i + 1; int L = i; dp[L, R] = maxPosSum + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } // Calculating the complete dp array for (int R = 0; R < N; R++) { for (int L = 0; L < N; L++) { // If length of subarray is less 3, then // continuing if (R - L + 1 < 3) continue; dp[L, R] = dp[L + 1, R - 1] + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } } // Updating the maxPosSum variable for (int L = 0; L < N; L++) { for (int R = L; R < N; R++) { maxPosSum = Math.Max(maxPosSum, dp[L, R]); } } // Returning the maximum possible sum of product return maxPosSum; } // Driver Code public static void Main() { // Given Input int[] A = { 5, 1, 2, 3 }, B = { 1, 4, 3, 2 }; Console.WriteLine(maxSum(A, B)); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript implementation of the above approach// Function to find the maximum sum of A[i]*B[i]// across all values of i from 0 to N-1 by reversing// at most one subarray of array Afunction maxSum(A, B){ var N = A.length; // Initialising maximum possible sum variable var maxPosSum = 0; var dp = Array(N).fill(0).map(x => Array(N).fill(0)); // Value of maxPosSum when no subarray is reversed for (var i = 0; i < N; i++) maxPosSum += A[i] * B[i]; // Initialising dp for subarray of length 1 for (var i = 0; i < N; i++) dp[i][i] = maxPosSum; // Initialising dp for subarray of length 2 for (var i = 0; i < N - 1; i++) { var R = i + 1; var L = i; dp[L][R] = maxPosSum + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } // Calculating the complete dp array for (var R = 0; R < N; R++) { for (var L = 0; L < N; L++) { // If length of subarray is less 3, then // continuing if (R - L + 1 < 3) continue; dp[L][R] = dp[L + 1][R - 1] + (A[R] * B[L]) - (A[L] * B[L]) + (A[L] * B[R]) - (A[R] * B[R]); } } // Updating the maxPosSum variable for (var L = 0; L < N; L++) { for (var R = L; R < N; R++) { maxPosSum = Math.max(maxPosSum, dp[L][R]); } } // Returning the maximum possible sum of product return maxPosSum;}// Driver Code// Given Inputvar A = [ 5, 1, 2, 3 ], B = [ 1, 4, 3, 2 ];document.write(maxSum(A, B));// This code is contributed by 29AjayKumar </script> |
Output
33
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
