Dada una array, necesitamos encontrar dos subarreglos con una longitud específica K tal que la suma de estos subarreglos sea máxima entre todas las opciones posibles de subarreglos.
Ejemplos:
Input : arr[] = [2, 5, 1, 2, 7, 3, 0]
K = 2
Output : 2 5
7 3
We can choose two arrays of maximum sum
as [2, 5] and [7, 3], the sum of these two
subarrays is maximum among all possible
choices of subarrays of length 2.
Input : arr[] = {10, 1, 3, 15, 30, 40, 4, 50, 2, 1}
K = 3
Output : 3 15 30
40 4 50
Podemos resolver este problema similar al método de dos punteros. Primero almacenamos la suma del prefijo en una array separada para que cualquier suma de subarreglo se pueda calcular en tiempo constante. Después de eso, inicializaremos nuestros dos subarreglo a partir de los índices (N – 2K) y (N – K), donde N es la longitud del arreglo y K es la longitud requerida del subarreglo. Luego, nos moveremos del índice (N – 2K) hacia 0 y cada vez verificaremos si la suma del subarreglo en el índice actual y la suma del subarreglo en (índice actual + K) es mayor que el subarreglo elegido previamente o no, si lo son, luego actualice el suma. Podemos ver aquí que como necesitamos maximizar nuestra suma, podemos tratar ambos subarreglos de forma independiente. En cada índice, verificaremos la suma del subarreglo en el índice actual y la suma del subarreglo a una distancia K y elegiremos la suma máxima de forma independiente y actualizaremos la respuesta final como la suma de ambos arreglos. En el código a continuación, el índice también se toma con la suma en forma de par para imprimir realmente los subarreglos. La complejidad temporal total de la solución será lineal.
Consulte el código a continuación para una mejor comprensión.
Implementación:
C++
// C++ program to get maximum sum two non-overlapping
// subarrays of same specified length
#include <bits/stdc++.h>
using namespace std;
// Utility method to get sum of subarray
// from index i to j
int getSubarraySum(int sum[], int i, int j)
{
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
// Method prints two non-overlapping subarrays of
// length K whose sum is maximum
void maximumSumTwoNonOverlappingSubarray(int arr[],
int N, int K)
{
int sum[N];
// filling prefix sum array
sum[0] = arr[0];
for (int i = 1; i < N; i++)
sum[i] = sum[i - 1] + arr[i];
// initializing subarrays from (N-2K) and (N-K) indices
pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
// initializing result sum from above subarray sums
int maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1) +
getSubarraySum(sum, N - K, N - 1);
// storing second subarray maximum and its starting index
pair<int, int> secondSubarrayMax = make_pair(N - K,
getSubarraySum(sum, N - K, N - 1));
// looping from N-2K-1 towards 0
for (int i = N - 2 * K - 1; i >= 0; i--)
{
// get subarray sum from (current index + K)
int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
// if (current index + K) sum is more then update
// secondSubarrayMax
if (cur >= secondSubarrayMax.second)
secondSubarrayMax = make_pair(i + K, cur);
// now getting complete sum (sum of both subarrays)
cur = getSubarraySum(sum, i, i + K - 1) +
secondSubarrayMax.second;
// if it is more then update main result
if (cur >= maxSum2Subarray)
{
maxSum2Subarray = cur;
resIndex = make_pair(i, secondSubarrayMax.first);
}
}
// printing actual subarrays
for (int i = resIndex.first; i < resIndex.first + K; i++)
cout << arr[i] << " ";
cout << endl;
for (int i = resIndex.second; i < resIndex.second + K; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code to test above methods
int main()
{
int arr[] = {2, 5, 1, 2, 7, 3, 0};
int N = sizeof(arr) / sizeof(int);
// K will be given such that (N >= 2K)
int K = 2;
maximumSumTwoNonOverlappingSubarray(arr, N, K);
return 0;
}
Java
// Java program to get maximum sum two non-overlapping
// subarrays of same specified length
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Utility method to get sum of subarray
// from index i to j
static int getSubarraySum(int sum[],
int i, int j)
{
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
// Method prints two non-overlapping subarrays of
// length K whose sum is maximum
static void maximumSumTwoNonOverlappingSubarray(int arr[],
int N, int K)
{
int []sum = new int[N];
// filling prefix sum array
sum[0] = arr[0];
for (int i = 1; i < N; i++)
sum[i] = sum[i - 1] + arr[i];
// initializing subarrays from
// (N-2K) and (N-K) indices
pair resIndex = new pair(N - 2 * K, N - K);
// initializing result sum from above subarray sums
int maxSum2Subarray = getSubarraySum(sum, N - 2 * K,
N - K - 1) +
getSubarraySum(sum, N - K, N - 1);
// storing second subarray maximum and
// its starting index
pair secondSubarrayMax = new pair(N - K,
getSubarraySum(sum, N - K, N - 1));
// looping from N-2K-1 towards 0
for (int i = N - 2 * K - 1; i >= 0; i--)
{
// get subarray sum from (current index + K)
int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
// if (current index + K) sum is more
// then update secondSubarrayMax
if (cur >= secondSubarrayMax.second)
secondSubarrayMax = new pair(i + K, cur);
// now getting complete sum (sum of both subarrays)
cur = getSubarraySum(sum, i, i + K - 1) +
secondSubarrayMax.second;
// if it is more then update main result
if (cur >= maxSum2Subarray)
{
maxSum2Subarray = cur;
resIndex = new pair(i, secondSubarrayMax.first);
}
}
// printing actual subarrays
for (int i = resIndex.first;
i < resIndex.first + K; i++)
System.out.print(arr[i] + " ");
System.out.println();
for (int i = resIndex.second;
i < resIndex.second + K; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code to test above methods
public static void main(String[] args)
{
int arr[] = {2, 5, 1, 2, 7, 3, 0};
int N = arr.length;
// K will be given such that (N >= 2K)
int K = 2;
maximumSumTwoNonOverlappingSubarray(arr, N, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to get maximum Sum two # non-overlapping subarrays of same specified length # Utility method to get Sum of # subarray from index i to j def getSubarraySum(Sum, i, j): if i == 0: return Sum[j] else: return Sum[j] - Sum[i - 1] # Method prints two non-overlapping subarrays # of length K whose Sum is maximum def maximumSumTwoNonOverlappingSubarray(arr, N, K): Sum = [None] * N # filling prefix Sum array Sum[0] = arr[0] for i in range(1, N): Sum[i] = Sum[i - 1] + arr[i] # Initializing subarrays from # (N-2K) and (N-K) indices resIndex = (N - 2 * K, N - K) # initializing result Sum from above subarray Sums maxSum2Subarray = (getSubarraySum(Sum, N - 2 * K, N - K - 1) + getSubarraySum(Sum, N - K, N - 1)) # storing second subarray maximum and its starting index secondSubarrayMax = (N - K, getSubarraySum(Sum, N - K, N - 1)) # looping from N-2K-1 towards 0 for i in range(N - 2 * K - 1, -1, -1): # get subarray Sum from (current index + K) cur = getSubarraySum(Sum, i + K, i + 2 * K - 1) # if (current index + K) Sum is more # than update secondSubarrayMax if cur >= secondSubarrayMax[1]: secondSubarrayMax = (i + K, cur) # now getting complete Sum (Sum of both subarrays) cur = (getSubarraySum(Sum, i, i + K - 1) + secondSubarrayMax[1]) # If it is more then update main result if cur >= maxSum2Subarray: maxSum2Subarray = cur resIndex = (i, secondSubarrayMax[0]) # printing actual subarrays for i in range(resIndex[0], resIndex[0] + K): print(arr[i], end = " ") print() for i in range(resIndex[1], resIndex[1] + K): print(arr[i], end = " ") print() # Driver Code if __name__ == "__main__": arr = [2, 5, 1, 2, 7, 3, 0] N = len(arr) # K will be given such that (N >= 2K) K = 2 maximumSumTwoNonOverlappingSubarray(arr, N, K) # This code is contributed by Rituraj Jain
C#
// C# program to get maximum sum two non-overlapping
// subarrays of same specified length
using System;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Utility method to get sum of subarray
// from index i to j
static int getSubarraySum(int []sum,
int i, int j)
{
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
// Method prints two non-overlapping subarrays of
// length K whose sum is maximum
static void maximumSumTwoNonOverlappingSubarray(int []arr,
int N, int K)
{
int []sum = new int[N];
// filling prefix sum array
sum[0] = arr[0];
for (int i = 1; i < N; i++)
sum[i] = sum[i - 1] + arr[i];
// initializing subarrays from
// (N-2K) and (N-K) indices
pair resIndex = new pair(N - 2 * K, N - K);
// initializing result sum from above subarray sums
int maxSum2Subarray = getSubarraySum(sum, N - 2 * K,
N - K - 1) +
getSubarraySum(sum, N - K, N - 1);
// storing second subarray maximum and
// its starting index
pair secondSubarrayMax = new pair(N - K,
getSubarraySum(sum, N - K, N - 1));
// looping from N-2K-1 towards 0
for (int i = N - 2 * K - 1; i >= 0; i--)
{
// get subarray sum from (current index + K)
int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
// if (current index + K) sum is more
// then update secondSubarrayMax
if (cur >= secondSubarrayMax.second)
secondSubarrayMax = new pair(i + K, cur);
// now getting complete sum (sum of both subarrays)
cur = getSubarraySum(sum, i, i + K - 1) +
secondSubarrayMax.second;
// if it is more then update main result
if (cur >= maxSum2Subarray)
{
maxSum2Subarray = cur;
resIndex = new pair(i, secondSubarrayMax.first);
}
}
// printing actual subarrays
for (int i = resIndex.first;
i < resIndex.first + K; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
for (int i = resIndex.second;
i < resIndex.second + K; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main(String[] args)
{
int []arr = {2, 5, 1, 2, 7, 3, 0};
int N = arr.Length;
// K will be given such that (N >= 2K)
int K = 2;
maximumSumTwoNonOverlappingSubarray(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to get maximum sum two non-overlapping
// subarrays of same specified length
// Utility method to get sum of subarray
// from index i to j
function getSubarraySum(sum, i, j) {
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
// Method prints two non-overlapping subarrays of
// length K whose sum is maximum
function maximumSumTwoNonOverlappingSubarray(arr, N, K) {
let sum = new Array(N);
// filling prefix sum array
sum[0] = arr[0];
for (let i = 1; i < N; i++)
sum[i] = sum[i - 1] + arr[i];
// initializing subarrays from (N-2K) and (N-K) indices
let resIndex = [N - 2 * K, N - K];
// initializing result sum from above subarray sums
let maxSum2Subarray = getSubarraySum(sum, N - 2 * K, N - K - 1) +
getSubarraySum(sum, N - K, N - 1);
// storing second subarray maximum and its starting index
let secondSubarrayMax = [N - K,
getSubarraySum(sum, N - K, N - 1)];
// looping from N-2K-1 towards 0
for (let i = N - 2 * K - 1; i >= 0; i--) {
// get subarray sum from (current index + K)
let cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
// if (current index + K) sum is more then update
// secondSubarrayMax
if (cur >= secondSubarrayMax[1])
secondSubarrayMax = [i + K, cur];
// now getting complete sum (sum of both subarrays)
cur = getSubarraySum(sum, i, i + K - 1) +
secondSubarrayMax[1];
// if it is more then update main result
if (cur >= maxSum2Subarray) {
maxSum2Subarray = cur;
resIndex = [i, secondSubarrayMax[0]];
}
}
// printing actual subarrays
for (let i = resIndex[0]; i < resIndex[0] + K; i++)
document.write(arr[i] + " ");
document.write("<br>");
for (let i = resIndex[1]; i < resIndex[1] + K; i++)
document.write(arr[i] + " ");
document.write("<br>");
}
// Driver code to test above methods
let arr = [2, 5, 1, 2, 7, 3, 0];
let N = arr.length;
// K will be given such that (N >= 2K)
let K = 2;
maximumSumTwoNonOverlappingSubarray(arr, N, K);
</script>
Producción
2 5 7 3
Complejidad de tiempo: O(n) , donde n es el tamaño de la array dada.
Espacio Auxiliar: O(n)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA