Dados dos arreglos X[] e Y[] de tamaño N , la tarea es encontrar el subarreglo más largo en X[] que contenga solo valores únicos , de modo que un subarreglo con índices similares en Y[] debería tener una suma máxima . El valor de los elementos de la array está en el rango [0, 1000] .
Ejemplos :
Entrada : N = 5,
X[] = {0, 1, 2, 0, 2},
Y[] = {5, 6, 7, 8, 22}
Salida : 21
Explicación : el subarreglo único más grande en X[] con suma máxima en Y[] es {1, 2, 0}.
Entonces, el subarreglo con los mismos índices en Y[] es {6, 7, 8}.
Por lo tanto, la suma máxima es 21.Entrada : N = 3,
X[] = {1, 1, 1},
Y[] = {2, 6, 7}
Salida : 7
Enfoque ingenuo: la tarea se puede resolver generando todos los subarreglos de la array X[] , verificando cada subarreglo si es válido y luego calculando la suma en la array para los índices correspondientes en Y.
Complejidad de Tiempo : O(N 3 )
Espacio Auxiliar : O(N)
Enfoque eficiente: la tarea se puede resolver utilizando el concepto de la ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Cree una array m de tamaño 1001 e inicialice todos los elementos como -1 . Para el índice i , m[i] almacena el índice en el que i está presente en el subarreglo. Si m[i] es -1, significa que el elemento no existe en el subarreglo.
- Inicialice low = 0, high = 0 , estos dos punteros definirán los índices del subarreglo actual.
- currSum y maxSum , definen la suma del subarreglo actual y la suma máxima en el arreglo.
- Itere sobre un bucle y verifique si el elemento actual en el índice alto ya existe en el subarreglo, si encuentra la suma de elementos en el subarreglo, actualice maxSum (si es necesario) y actualice bajo. Ahora, finalmente, muévase al siguiente elemento incrementando high .
- Tenga en cuenta que encontrará un caso de esquina que puede dar como resultado una respuesta incorrecta, por ejemplo, consideremos nuestra primera Entrada, luego el subarreglo {8, 2} es la opción correcta y 30 es nuestra respuesta correcta. Así que maneje ese caso de esquina por separado sumando todos los elementos desde el anterior bajo hasta el alto .
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 find the max sum
int findMaxSumSubarray(int X[], int Y[],
int N)
{
// Array to store the elements
// and their indices
int m[1001];
// Initialize all elements as -1
for (int i = 0; i < 1001; i++)
m[i] = -1;
// low and high represent
// beginning and end of subarray
int low = 0, high = 0;
int currSum = 0, maxSum = 0;
// Iterate through the array
// Note that the array is traversed till high <= N
// so that the corner case can be handled
while (high <= N) {
if(high==N){
//Calculate the currSum for the subarray
//after the last updated low to high-1
currSum=0;
for (int i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = max(maxSum, currSum);
break;
}
// If the current element already
// exists in the current subarray
if (m[X[high]] != -1
&& m[X[high]] >= low) {
currSum = 0;
// Calculate the sum
// of current subarray
for (int i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = max(maxSum, currSum);
// Starting index of new subarray
low = m[X[high]] + 1;
}
// Keep expanding the subarray
// and mark the index
m[X[high]] = high;
high++;
}
// Return the maxSum
return maxSum;
}
// Driver code
int main()
{
int X[] = { 0, 1, 2, 0, 2 };
int Y[] = { 5, 6, 7, 8, 22 };
int N = sizeof(X) / sizeof(X[0]);
// Function call to find the sum
int maxSum = findMaxSumSubarray(X, Y, N);
// Print the result
cout << maxSum << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the max sum
static int findMaxSumSubarray(int X[], int Y[],
int N)
{
// Array to store the elements
// and their indices
int m[] = new int[1001];
// Initialize all elements as -1
for (int i = 0; i < 1001; i++)
m[i] = -1;
// low and high represent
// beginning and end of subarray
int low = 0, high = 0;
int currSum = 0, maxSum = 0;
// Iterate through the array
// Note that the array is traversed till high <= N
// so that the corner case can be handled
while (high <= N) {
if(high==N){
// Calculate the currSum for the subarray
// after the last updated low to high-1
currSum = 0;
for (int i = low; i <= high - 1;i++)
currSum += Y[i];
// Find the maximum sum
maxSum = Math.max(maxSum, currSum);
break;
}
// If the current element already
// exists in the current subarray
if (m[X[high]] != -1
&& m[X[high]] >= low) {
currSum = 0;
// Calculate the sum
// of current subarray
for (int i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = Math.max(maxSum, currSum);
// Starting index of new subarray
low = m[X[high]] + 1;
}
// Keep expanding the subarray
// and mark the index
m[X[high]] = high;
high++;
}
// Return the maxSum
return maxSum;
}
// Driver code
public static void main(String args[])
{
int X[] = { 0, 1, 2, 0, 2 };
int Y[] = { 5, 6, 7, 8, 22 };
int N = X.length;
// Function call to find the sum
int maxSum = findMaxSumSubarray(X, Y, N);
// Print the result
System.out.println(maxSum);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python code for the above approach # Function to find the max sum def findMaxSumSubarray(X, Y, N): # Array to store the elements # and their indices m = [0] * (1001); # Initialize all elements as -1 for i in range(1001): m[i] = -1; # low and high represent # beginning and end of subarray low = 0 high = 0 currSum = 0 maxSum = 0; # Iterate through the array # Note that the array is traversed till high <= N # so that the corner case can be handled while (high <= N): if(high == N): currSum=0; # Calculate the currSum for the subarray # after the last updated low to high-1 for i in range(low, high): currSum += Y[i]; maxSum = max(maxSum, currSum); break; # If the current element already # exists in the current subarray if (m[X[high]] != -1 and m[X[high]] >= low): currSum = 0; # Calculate the sum # of current subarray for i in range(low, high): currSum += Y[i]; # Find the maximum sum maxSum = max(maxSum, currSum); # Starting index of new subarray low = m[X[high]] + 1; # Keep expanding the subarray # and mark the index m[X[high]] = high; high += 1 # Return the maxSum return maxSum; # Driver code X = [0, 1, 2, 0, 2]; Y = [5, 6, 7, 8, 22]; N = len(X) # Function call to find the sum maxSum = findMaxSumSubarray(X, Y, N); # Print the result print(maxSum, end="") # This code is contributed by Saurabh Jaiswal
C#
// C# program for above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the max sum
static int findMaxSumSubarray(int[] X, int[] Y, int N)
{
// Array to store the elements
// and their indices
int[] m = new int[1001];
// Initialize all elements as -1
for (int i = 0; i < 1001; i++)
m[i] = -1;
// low and high represent
// beginning and end of subarray
int low = 0, high = 0;
int currSum = 0, maxSum = 0;
// Iterate through the array
// Note that the array is traversed till high <= N
// so that the corner case can be handled
while (high <= N)
{
if(high==N){
// Calculate the currSum for the subarray
// after the last updated low to high-1
currSum=0;
for (int i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = Math.Max(maxSum, currSum);
break;
}
// If the current element already
// exists in the current subarray
if (m[X[high]] != -1
&& m[X[high]] >= low) {
currSum = 0;
// Calculate the sum
// of current subarray
for (int i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = Math.Max(maxSum, currSum);
// Starting index of new subarray
low = m[X[high]] + 1;
}
// Keep expanding the subarray
// and mark the index
m[X[high]] = high;
high++;
}
// Return the maxSum
return maxSum;
}
// Driver code
static public void Main ()
{
int[] X = { 0, 1, 2, 0, 2 };
int[] Y = { 5, 6, 7, 8, 22 };
int N = X.Length;
// Function call to find the sum
int maxSum = findMaxSumSubarray(X, Y, N);
// Print the result
Console.WriteLine(maxSum);
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the max sum
function findMaxSumSubarray(X, Y, N)
{
// Array to store the elements
// and their indices
let m = new Array(1001);
// Initialize all elements as -1
for (let i = 0; i < 1001; i++)
m[i] = -1;
// low and high represent
// beginning and end of subarray
let low = 0, high = 0;
let currSum = 0, maxSum = 0;
// Iterate through the array
// Note that the array is traversed till high <= N
// so that the corner case can be handled
while (high <= N)
{
if(high==N){
// Calculate the currSum for the subarray
// after the last updated low to high-1
currSum=0;
for (let i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = Math.max(maxSum, currSum);
break;
}
// If the current element already
// exists in the current subarray
if (m[X[high]] != -1
&& m[X[high]] >= low) {
currSum = 0;
// Calculate the sum
// of current subarray
for (let i = low; i <= high - 1;
i++)
currSum += Y[i];
// Find the maximum sum
maxSum = Math.max(maxSum, currSum);
// Starting index of new subarray
low = m[X[high]] + 1;
}
// Keep expanding the subarray
// and mark the index
m[X[high]] = high;
high++;
}
// Return the maxSum
return maxSum;
}
// Driver code
let X = [0, 1, 2, 0, 2];
let Y = [5, 6, 7, 8, 22];
let N = X.length
// Function call to find the sum
let maxSum = findMaxSumSubarray(X, Y, N);
// Print the result
document.write(maxSum + '<br>')
// This code is contributed by Potta Lokesh
</script>
Producción
30
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA