Dadas dos arrays A[] y B[] , ambas formadas por N enteros positivos, la tarea es encontrar la puntuación máxima entre todas las posibles subarreglas con el mismo índice en ambas arrays , de modo que la puntuación de cualquier subarreglo sobre el rango [L, R] se calcula por el máximo de los valores (A L *B L + A L + 1 *B L + 1 + … + A R *B R ) + (A R *B L + A R – 1 *B L + 1 + … + A L * Br ) .
Ejemplos:
Entrada: A[] = {13, 4, 5}, B[] = {10, 22, 2}
Salida: 326
Explicación:
Considere los subarreglos {A[0], A[1]} y {B[0] , B[1]} . La puntuación de estos subarreglos se puede calcular como el máximo de las siguientes dos expresiones:
- El valor de la expresión (A 0 *B 0 + A 1 *B 1 ) = 13 * 1 + 4 * 22 = 218.
- El valor de la expresión (A 0 *B 1 + A 1 *B 0 ) = 13 * 1 + 4 * 22 = 326.
Por lo tanto, el valor máximo de las dos expresiones anteriores es 326, que es la puntuación máxima entre todos los subarreglos posibles.
Entrada: A[] = {9, 8, 7, 6, 1}, B[]={6, 7, 8, 9, 1}
Salida: 230
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos correspondientes posibles y almacenar todos los puntajes de todos los subarreglos generados utilizando los criterios dados. Después de almacenar todos los puntajes, imprima el valor máximo entre todos los puntajes generados.
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 calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
int currSubArrayScore(int* a, int* b,
int l, int r)
{
int straightScore = 0;
int reverseScore = 0;
// Traverse the current subarray
for (int i = l; i <= r; i++) {
// Finding the score without
// reversing the subarray
straightScore += a[i] * b[i];
// Calculating the score of
// the reversed subarray
reverseScore += a[r - (i - l)]
* b[i];
}
// Return the score of subarray
return max(straightScore,
reverseScore);
}
// Function to find the subarray with
// the maximum score
void maxScoreSubArray(int* a, int* b,
int n)
{
// Stores the maximum score and the
// starting and the ending point
// of subarray with maximum score
int res = 0, start = 0, end = 0;
// Traverse all the subarrays
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Store the score of the
// current subarray
int currScore
= currSubArrayScore(
a, b, i, j);
// Update the maximum score
if (currScore > res) {
res = currScore;
start = i;
end = j;
}
}
}
// Print the maximum score
cout << res;
}
// Driver Code
int main()
{
int A[] = { 13, 4, 5 };
int B[] = { 10, 22, 2 };
int N = sizeof(A) / sizeof(A[0]);
maxScoreSubArray(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
static int currSubArrayScore(int[] a, int[] b,
int l, int r)
{
int straightScore = 0;
int reverseScore = 0;
// Traverse the current subarray
for(int i = l; i <= r; i++)
{
// Finding the score without
// reversing the subarray
straightScore += a[i] * b[i];
// Calculating the score of
// the reversed subarray
reverseScore += a[r - (i - l)] * b[i];
}
// Return the score of subarray
return Math.max(straightScore, reverseScore);
}
// Function to find the subarray with
// the maximum score
static void maxScoreSubArray(int[] a, int[] b, int n)
{
// Stores the maximum score and the
// starting and the ending point
// of subarray with maximum score
int res = 0, start = 0, end = 0;
// Traverse all the subarrays
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
// Store the score of the
// current subarray
int currScore = currSubArrayScore(a, b, i, j);
// Update the maximum score
if (currScore > res)
{
res = currScore;
start = i;
end = j;
}
}
}
// Print the maximum score
System.out.print(res);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 13, 4, 5 };
int B[] = { 10, 22, 2 };
int N = A.length;
maxScoreSubArray(A, B, N);
}
}
// This code is contributed by subhammahato348
Python3
# Python program for the above approach # Function to calculate the score # of same-indexed subarrays selected # from the arrays a[] and b[] def currSubArrayScore(a, b, l, r): straightScore = 0 reverseScore = 0 # Traverse the current subarray for i in range(l, r+1) : # Finding the score without # reversing the subarray straightScore += a[i] * b[i] # Calculating the score of # the reversed subarray reverseScore += a[r - (i - l)] * b[i] # Return the score of subarray return max(straightScore, reverseScore) # Function to find the subarray with # the maximum score def maxScoreSubArray(a, b, n) : # Stores the maximum score and the # starting and the ending point # of subarray with maximum score res = 0 start = 0 end = 0 # Traverse all the subarrays for i in range(n) : for j in range(i, n) : # Store the score of the # current subarray currScore = currSubArrayScore(a, b, i, j) # Update the maximum score if (currScore > res) : res = currScore start = i end = j # Print the maximum score print(res) # Driver Code A = [ 13, 4, 5 ] B = [ 10, 22, 2 ] N = len(A) maxScoreSubArray(A, B, N) # This code is contributed by target_2.
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
static int currSubArrayScore(int[] a, int[] b,
int l, int r)
{
int straightScore = 0;
int reverseScore = 0;
// Traverse the current subarray
for(int i = l; i <= r; i++)
{
// Finding the score without
// reversing the subarray
straightScore += a[i] * b[i];
// Calculating the score of
// the reversed subarray
reverseScore += a[r - (i - l)] * b[i];
}
// Return the score of subarray
return Math.Max(straightScore, reverseScore);
}
// Function to find the subarray with
// the maximum score
static void maxScoreSubArray(int[] a, int[] b, int n)
{
// Stores the maximum score and the
// starting and the ending point
// of subarray with maximum score
int res = 0;
// Traverse all the subarrays
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
// Store the score of the
// current subarray
int currScore = currSubArrayScore(
a, b, i, j);
// Update the maximum score
if (currScore > res)
{
res = currScore;
}
}
}
// Print the maximum score
Console.Write(res);
}
// Driver Code
static public void Main()
{
int[] A = { 13, 4, 5 };
int[] B = { 10, 22, 2 };
int N = A.Length;
maxScoreSubArray(A, B, N);
}
}
// This code is contributed by unknown2108
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
function currSubArrayScore(a, b, l, r)
{
let straightScore = 0;
let reverseScore = 0;
// Traverse the current subarray
for (let i = l; i <= r; i++) {
// Finding the score without
// reversing the subarray
straightScore += a[i] * b[i];
// Calculating the score of
// the reversed subarray
reverseScore += a[r - (i - l)]
* b[i];
}
// Return the score of subarray
return Math.max(straightScore,
reverseScore);
}
// Function to find the subarray with
// the maximum score
function maxScoreSubArray(a, b, n) {
// Stores the maximum score and the
// starting and the ending point
// of subarray with maximum score
let res = 0, start = 0, end = 0;
// Traverse all the subarrays
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
// Store the score of the
// current subarray
let currScore
= currSubArrayScore(
a, b, i, j);
// Update the maximum score
if (currScore > res) {
res = currScore;
start = i;
end = j;
}
}
}
// Print the maximum score
document.write(res);
}
// Driver Code
let A = [13, 4, 5];
let B = [10, 22, 2];
let N = A.length;
maxScoreSubArray(A, B, N);
// This code is contributed by gfgking.
</script>
Producción:
326
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar al considerar cada elemento como el punto medio de cada subarreglo posible y luego expandir el subarreglo en ambas direcciones mientras se actualiza la puntuación máxima para cada valor. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res para almacenar el valor máximo resultante.
- Iterar sobre el rango [1, N – 1] usando la variable mid y realizar los siguientes pasos:
- Inicialice dos variables, digamos score1 y score2 como A[mid]*B[mid] en caso de subarreglo de longitud impar.
- Inicialice dos variables, diga anterior como (mid – 1) y siguiente como (mid + 1) para expandir el subarreglo actual.
- Itere un ciclo hasta que prev sea positivo y el valor de next sea menor que N y realice los siguientes pasos:
- Agregue el valor de (a[anterior]*b[anterior]+a[siguiente]*b[siguiente]) a la variable score1 .
- Agregue el valor de (a[anterior]*b[siguiente]+a[siguiente]*b[anterior]) a la variable score2 .
- Actualice el valor de res al máximo de score1 , score2 y res .
- Disminuya el valor de prev en 1 e incremente el valor de next en 1 .
- Actualice el valor de score1 y score2 como 0 y establezca el valor de prev como (mid – 1) y next como mid para considerar el caso de un subarreglo de longitud uniforme.
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
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 calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
void maxScoreSubArray(int* a, int* b,
int n)
{
// Store the required result
int res = 0;
// Iterate in the range [0, N-1]
for (int mid = 0; mid < n; mid++) {
// Consider the case of odd
// length subarray
int straightScore = a[mid] * b[mid],
reverseScore = a[mid] * a[mid];
int prev = mid - 1, next = mid + 1;
// Update the maximum score
res = max(res, max(straightScore,
reverseScore));
// Expanding the subarray in both
// directions with equal length
// so that mid point remains same
while (prev >= 0 && next < n) {
// Update both the scores
straightScore
+= (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore
+= (a[prev] * b[next]
+ a[next] * b[prev]);
res = max(res,
max(straightScore,
reverseScore));
prev--;
next++;
}
// Consider the case of
// even length subarray
straightScore = 0;
reverseScore = 0;
prev = mid - 1, next = mid;
while (prev >= 0 && next < n) {
// Update both the scores
straightScore
+= (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore
+= (a[prev] * b[next]
+ a[next] * b[prev]);
res = max(res,
max(straightScore,
reverseScore));
prev--;
next++;
}
}
// Print the result
cout << res;
}
// Driver Code
int main()
{
int A[] = { 13, 4, 5 };
int B[] = { 10, 22, 2 };
int N = sizeof(A) / sizeof(A[0]);
maxScoreSubArray(A, B, N);
return 0;
}
Java
// Java Program for the above approach
import java.io.*;
class GFG {
// Function to calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
static void maxScoreSubArray(int[] a, int[] b, int n)
{
// Store the required result
int res = 0;
// Iterate in the range [0, N-1]
for (int mid = 0; mid < n; mid++) {
// Consider the case of odd
// length subarray
int straightScore = a[mid] * b[mid],
reverseScore = a[mid] * a[mid];
int prev = mid - 1, next = mid + 1;
// Update the maximum score
res = Math.max(
res, Math.max(straightScore, reverseScore));
// Expanding the subarray in both
// directions with equal length
// so that mid point remains same
while (prev >= 0 && next < n) {
// Update both the scores
straightScore += (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore += (a[prev] * b[next]
+ a[next] * b[prev]);
res = Math.max(res, Math.max(straightScore,
reverseScore));
prev--;
next++;
}
// Consider the case of
// even length subarray
straightScore = 0;
reverseScore = 0;
prev = mid - 1;
next = mid;
while (prev >= 0 && next < n) {
// Update both the scores
straightScore += (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore += (a[prev] * b[next]
+ a[next] * b[prev]);
res = Math.max(res, Math.max(straightScore,
reverseScore));
prev--;
next++;
}
}
// Print the result
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 13, 4, 5 };
int B[] = { 10, 22, 2 };
int N = A.length;
maxScoreSubArray(A, B, N);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program for the above approach # Function to calculate the score # of same-indexed subarrays selected # from the arrays a[] and b[] def maxScoreSubArray(a, b, n): # Store the required result res = 0 # Iterate in the range [0, N-1] for mid in range(n): # Consider the case of odd # length subarray straightScore = a[mid] * b[mid] reverseScore = a[mid] * a[mid] prev = mid - 1 next = mid + 1 # Update the maximum score res = max(res, max(straightScore, reverseScore)) # Expanding the subarray in both # directions with equal length # so that mid poremains same while (prev >= 0 and next < n): # Update both the scores straightScore += (a[prev] * b[prev] + a[next] * b[next]) reverseScore += (a[prev] * b[next] + a[next] * b[prev]) res = max(res, max(straightScore, reverseScore)) prev -= 1 next += 1 # Consider the case of # even length subarray straightScore = 0 reverseScore = 0 prev = mid - 1 next = mid while (prev >= 0 and next < n): # Update both the scores straightScore += (a[prev] * b[prev] + a[next] * b[next]) reverseScore += (a[prev] * b[next] + a[next] * b[prev]) res = max(res, max(straightScore, reverseScore)) prev -= 1 next += 1 # Print the result print(res) # Driver Code if __name__ == '__main__': A = [ 13, 4, 5 ] B = [ 10, 22, 2 ] N = len(A) maxScoreSubArray(A, B, N) # This code is contributed by mohit kumar 29
C#
// C# Program for the above approach
using System;
public class GFG{
// Function to calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
static void maxScoreSubArray(int[] a, int[] b, int n)
{
// Store the required result
int res = 0;
// Iterate in the range [0, N-1]
for (int mid = 0; mid < n; mid++) {
// Consider the case of odd
// length subarray
int straightScore = a[mid] * b[mid],
reverseScore = a[mid] * a[mid];
int prev = mid - 1, next = mid + 1;
// Update the maximum score
res = Math.Max(
res, Math.Max(straightScore, reverseScore));
// Expanding the subarray in both
// directions with equal length
// so that mid point remains same
while (prev >= 0 && next < n) {
// Update both the scores
straightScore += (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore += (a[prev] * b[next]
+ a[next] * b[prev]);
res = Math.Max(res, Math.Max(straightScore,
reverseScore));
prev--;
next++;
}
// Consider the case of
// even length subarray
straightScore = 0;
reverseScore = 0;
prev = mid - 1;
next = mid;
while (prev >= 0 && next < n) {
// Update both the scores
straightScore += (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore += (a[prev] * b[next]
+ a[next] * b[prev]);
res = Math.Max(res, Math.Max(straightScore,
reverseScore));
prev--;
next++;
}
}
// Print the result
Console.WriteLine(res);
}
// Driver Code
static public void Main (){
int[] A = { 13, 4, 5 };
int[] B = { 10, 22, 2 };
int N = A.Length;
maxScoreSubArray(A, B, N);
}
}
// This code is contributed by patel2127.
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate the score
// of same-indexed subarrays selected
// from the arrays a[] and b[]
function maxScoreSubArray(a, b, n) {
// Store the required result
let res = 0;
// Iterate in the range [0, N-1]
for (let mid = 0; mid < n; mid++) {
// Consider the case of odd
// length subarray
let straightScore = a[mid] * b[mid],
reverseScore = a[mid] * a[mid];
let prev = mid - 1, next = mid + 1;
// Update the maximum score
res = Math.max(res, Math.max(straightScore,
reverseScore));
// Expanding the subarray in both
// directions with equal length
// so that mid point remains same
while (prev >= 0 && next < n) {
// Update both the scores
straightScore
+= (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore
+= (a[prev] * b[next]
+ a[next] * b[prev]);
res = Math.max(res,
Math.max(straightScore,
reverseScore));
prev--;
next++;
}
// Consider the case of
// even length subarray
straightScore = 0;
reverseScore = 0;
prev = mid - 1, next = mid;
while (prev >= 0 && next < n) {
// Update both the scores
straightScore
+= (a[prev] * b[prev]
+ a[next] * b[next]);
reverseScore
+= (a[prev] * b[next]
+ a[next] * b[prev]);
res = Math.max(res,
Math.max(straightScore,
reverseScore));
prev--;
next++;
}
}
// Print the result
document.write(res);
}
// Driver Code
let A = [13, 4, 5];
let B = [10, 22, 2];
let N = A.length
maxScoreSubArray(A, B, N);
</script>
Producción:
326
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA