Dados dos arreglos arr[] y brr[] de tamaño N y M enteros respectivamente, la tarea es maximizar la suma del producto de los mismos elementos indexados de dos subarreglos de igual longitud con el subarreglo seleccionado del arreglo brr[ ] siendo invertido .
Ejemplos:
Entrada: arr[] = {-1, 3, -2, 4, 5}, brr[] = {4, -5}
Salida: 26
Explicación:
Los subarreglos seleccionados de la array arr[] y brr[] son {- 2, 4} y {4, -5}.
Por lo tanto, suma del producto de elementos del mismo índice = (-2)*(-5) + 4*4 = 26.Entrada: arr[] = {1, 1, 1}, brr[] = {1, 1, 1}
Salida: 3
Enfoque: el problema dado se puede resolver almacenando el producto de cada elemento de los dos arreglos en una array 2D y encontrar el subarreglo con la suma máxima en cada una de las diagonales derechas de esta array 2D, que es similar a encontrar el subarreglo de suma máxima en la array . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D mat[][] de tamaño N*M para almacenar el producto de cada elemento de las dos arrays.
- Genere todos los pares posibles a partir de los arreglos dados arr[] y brr[] y guárdelos en la array 2D mat[][] .
- Ahora, para una misma longitud del subarreglo, la idea es recorrer las diagonales de la array a partir de la primera fila y la primera columna.
- Después de cada recorrido de la diagonal , almacene los elementos en una array y luego encuentre el subarreglo de suma máxima de los elementos almacenados en la array.
- Después de los pasos anteriores, imprima la suma máxima entre todas las sumas máximas obtenidas en los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
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 arrays
void 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 matrix
void 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 0
void 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 Code
int 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 approach
import 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 arrays def 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 matrix def 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 0 def 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 Code if __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 approach
using 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>
Producción:
26
Complejidad Temporal: O(N 2 )
Espacio Auxiliar: O(N 2 ), ya que se ha tomado N 2 espacio extra.
Publicación traducida automáticamente
Artículo escrito por swatijha0908 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA