Given two arrays arr[] and brr[] of size N and M integers respectively, the task is to maximize the sum of the product of the same-indexed elements of two subarrays of an equal length with the selected subarray from the array brr[] being reversed.
Examples:
Input: arr[] = {-1, 3, -2, 4, 5}, brr[] = {4, -5}
Output: 26
Explanation:
Subarrays selected from the array arr[] and brr[] are {-2, 4} and {4, -5}.
Therefore, sum of the product of same-indexed elements = (-2)*(-5) + 4*4 = 26.Input: arr[] = {1, 1, 1}, brr[] = {1, 1, 1}
Output: 3
Approach: The given problem can be solved by storing the product of each element from the two arrays in a 2D matrix and find the subarray with the maximum sum in each of the right diagonals of this 2D matrix which is similar to finding the maximum sum subarray in the array. Follow the steps below to solve the problem:
- Initialize a 2D matrix mat[][] of size N*M to store the product of each element from the two arrays.
- Generate all possible pairs from the given arrays arr[] and brr[] and store them in the 2D matrix mat[][].
- Now, for an equal length of the subarray, the idea is to traverse the diagonals of the matrix starting from the first row and first column.
- After every traversal of the diagonal store the elements in an array and then find the maximum sum subarray of the elements stored in the array.
- After the above steps, print the maximum sum among all the maximum sum obtained in the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to store product of each// pair of elements from two arraysvoid store_in_matrix(int a[], int b[], int n1, int n2, int mat[][10]){ // Store product of pairs // of elements in a matrix for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { mat[i][j] = (a[i] * b[j]); } }}// Function to find the maximum subarray// sum in every right diagonal of the matrixvoid maxsum_rt_diag(int n1, int n2, int mat[][10], int& ans){ // Stores maximum continuous sum int max_ending_here; int i, j; // Start with each element // from the last column for (int t = 0; t < n1; t++) { i = t; j = n2 - 1; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i][j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset it to 0 max_ending_here = 0; } } // Start with each element // from the first row for (int t = 0; t < n2; t++) { i = 0; j = t; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i][j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset to 0 max_ending_here = 0; } }}// Function to initialize matrix to 0void initMatrix(int mat[10][10], int n1, int n2){ // Traverse each row for (int i = 0; i < n1; i++) { // Traverse each column for (int j = 0; j < n2; j++) { mat[i][j] = 0; } }}// Function to find the maximum sum of// the two equal subarray selected from// the given two arrays a[] and b[]void findMaxProduct(int a[], int n1, int b[], int n2){ // Stores the matrix int mat[10][10]; // Initialize each element in mat[] to 0 initMatrix(mat, n1, n2); // Store product of each element // from two arrays in a matrix store_in_matrix(a, b, n1, n2, mat); // Stores the result int ans = 0; // Find maximum subarray sum in // every right diagonal of matrix maxsum_rt_diag(n1, n2, mat, ans); // Print the maximum sum cout << ans << "\n";}// Driver Codeint main(){ // Initialize two arrays int arr[] = { -1, 3, -2, 4, 5 }; int brr[] = { 4, -5 }; // Find size of array int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(brr) / sizeof(brr[0]); // Function Call findMaxProduct(arr, N, brr, M); return 0;} |
Java
// java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to store product of each // pair of elements from two arrays static void store_in_matrix(int a[], int b[], int n1, int n2, int mat[][]) { // Store product of pairs // of elements in a matrix for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { mat[i][j] = (a[i] * b[j]); } } } // Function to find the maximum subarray // sum in every right diagonal of the matrix static int maxsum_rt_diag(int n1, int n2, int mat[][]) { // Stores maximum continuous sum int max_ending_here; int i, j; // Stores the result int ans = 0; // Start with each element // from the last column for (int t = 0; t < n1; t++) { i = t; j = n2 - 1; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i][j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset it to 0 max_ending_here = 0; } } // Start with each element // from the first row for (int t = 0; t < n2; t++) { i = 0; j = t; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i][j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset to 0 max_ending_here = 0; } } return ans; } // Function to find the maximum sum of // the two equal subarray selected from // the given two arrays a[] and b[] static void findMaxProduct(int a[], int n1, int b[], int n2) { // Stores the matrix int mat[][] = new int[10][10]; // Store product of each element // from two arrays in a matrix store_in_matrix(a, b, n1, n2, mat); // Stores the result int ans = 0; // Find maximum subarray sum in // every right diagonal of matrix ans = maxsum_rt_diag(n1, n2, mat); // Print the maximum sum System.out.println(ans); } // Driver Code public static void main(String[] args) { // Initialize two arrays int arr[] = { -1, 3, -2, 4, 5 }; int brr[] = { 4, -5 }; // Find size of array int N = arr.length; int M = brr.length; // Function Call findMaxProduct(arr, N, brr, M); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to store product of each# pair of elements from two arraysdef store_in_matrix(a, b, n1, n2, mat): # Store product of pairs # of elements in a matrix for i in range(n1): for j in range(n2): mat[i][j] = (a[i] * b[j])# Function to find the maximum subarray# sum in every right diagonal of the matrixdef maxsum_rt_diag(n1, n2, mat, ans): # Stores maximum continuous sum max_ending_here=0 i, j = 0, 0 # Start with each element # from the last column for t in range(n1): i = t j = n2 - 1 max_ending_here = 0 # Check for each diagonal while (i < n1 and j >= 0): max_ending_here = max_ending_here + mat[i][j] i += 1 j -= 1 # Update ans if max_ending_here # is greater than ans if (ans < max_ending_here): ans = max_ending_here # If max_ending_here is -ve if (max_ending_here < 0): # Reset it to 0 max_ending_here = 0 # Start with each element # from the first row for t in range(n2): i = 0 j = t max_ending_here = 0 # Check for each diagonal while (i < n1 and j >= 0): max_ending_here = max_ending_here + mat[i][j] i += 1 j -= 1 # Update ans if max_ending_here # is greater than ans if (ans < max_ending_here): ans = max_ending_here # If max_ending_here is -ve if (max_ending_here < 0): # Reset to 0 max_ending_here = 0 return ans# Function to initialize matrix to 0def initMatrix(mat, n1, n2): # Traverse each row for i in range(n1): # Traverse each column for j in range(n2): mat[i][j] = 0# Function to find the maximum sum of# the two equal subarray selected from# the given two arrays a[] and b[]def findMaxProduct(a, n1, b, n2): # Stores the matrix mat = [[ 0 for i in range(10)] for i in range(10)] # Initialize each element in mat[] to 0 initMatrix(mat, n1, n2) # Store product of each element # from two arrays in a matrix store_in_matrix(a, b, n1, n2, mat) # Stores the result ans = 0 # Find maximum subarray sum in # every right diagonal of matrix ans = maxsum_rt_diag(n1, n2, mat, ans) # Print the maximum sum print (ans)# Driver Codeif __name__ == '__main__': # Initialize two arrays arr= [-1, 3, -2, 4, 5] brr= [4, -5] # Find size of array N = len(arr) M = len(brr) # Function Call findMaxProduct(arr, N, brr, M)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG { // Function to store product of each // pair of elements from two arrays static void store_in_matrix(int[] a, int[] b, int n1, int n2, int[, ] mat) { // Store product of pairs // of elements in a matrix for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { mat[i, j] = (a[i] * b[j]); } } } // Function to find the maximum subarray // sum in every right diagonal of the matrix static int maxsum_rt_diag(int n1, int n2, int[, ] mat) { // Stores maximum continuous sum int max_ending_here; int i, j; // Stores the result int ans = 0; // Start with each element // from the last column for (int t = 0; t < n1; t++) { i = t; j = n2 - 1; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i, j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset it to 0 max_ending_here = 0; } } // Start with each element // from the first row for (int t = 0; t < n2; t++) { i = 0; j = t; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i, j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset to 0 max_ending_here = 0; } } return ans; } // Function to find the maximum sum of // the two equal subarray selected from // the given two arrays a[] and b[] static void findMaxProduct(int[] a, int n1, int[] b, int n2) { // Stores the matrix int[, ] mat = new int[10, 10]; // Store product of each element // from two arrays in a matrix store_in_matrix(a, b, n1, n2, mat); // Stores the result int ans = 0; // Find maximum subarray sum in // every right diagonal of matrix ans = maxsum_rt_diag(n1, n2, mat); // Print the maximum sum Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { // Initialize two arrays int[] arr = { -1, 3, -2, 4, 5 }; int[] brr = { 4, -5 }; // Find size of array int N = arr.Length; int M = brr.Length; // Function Call findMaxProduct(arr, N, brr, M); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program implementation// of the approach // Function to store product of each // pair of elements from two arrays function store_in_matrix(a, b, n1, n2, mat) { // Store product of pairs // of elements in a matrix for (let i = 0; i < n1; i++) { for (let j = 0; j < n2; j++) { mat[i][j] = (a[i] * b[j]); } } } // Function to find the maximum subarray // sum in every right diagonal of the matrix function maxsum_rt_diag(n1, n2, mat) { // Stores maximum continuous sum let max_ending_here; let i, j; // Stores the result let ans = 0; // Start with each element // from the last column for (let t = 0; t < n1; t++) { i = t; j = n2 - 1; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i][j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset it to 0 max_ending_here = 0; } } // Start with each element // from the first row for (let t = 0; t < n2; t++) { i = 0; j = t; max_ending_here = 0; // Check for each diagonal while (i < n1 && j >= 0) { max_ending_here = max_ending_here + mat[i][j]; i++; j--; // Update ans if max_ending_here // is greater than ans if (ans < max_ending_here) ans = max_ending_here; // If max_ending_here is -ve if (max_ending_here < 0) // Reset to 0 max_ending_here = 0; } } return ans; } // Function to find the maximum sum of // the two equal subarray selected from // the given two arrays a[] and b[] function findMaxProduct(a, n1, b, n2) { // Stores the matrix let mat = new Array(10); for (var i = 0; i < mat.length; i++) { mat[i] = new Array(2); } // Store product of each element // from two arrays in a matrix store_in_matrix(a, b, n1, n2, mat); // Stores the result let ans = 0; // Find maximum subarray sum in // every right diagonal of matrix ans = maxsum_rt_diag(n1, n2, mat); // Print the maximum sum document.write(ans); }// Driver Code // Initialize two arrays let arr = [ -1, 3, -2, 4, 5 ]; let brr = [ 4, -5 ]; // Find size of array let N = arr.length; let M = brr.length; // Function Call findMaxProduct(arr, N, brr, M); // This code is contributed by souravghosh0416.</script> |
Output:
26
Time Complexity: O(N2)
Auxiliary Space: O(N2), since N2 extra space has been taken.
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!
