Dada una array y dos números M y K. Necesitamos encontrar la suma de M subarreglos máximos de tamaño K (no superpuestos) en la array. (El orden de la array permanece sin cambios). K es el tamaño de los subarreglos y M es el número de subarreglos. Se puede suponer que el tamaño de la array es mayor que m*k. Si el tamaño total de la array no es múltiplo de k, entonces podemos tomar la última array parcial.
Ejemplos:
Input: N = 7, M = 3, K = 1
arr[] = {2, 10, 7, 18, 5, 33, 0};
Output: 61
Explanation: subsets are: 33, 18, 10 (3 subsets of size 1)
Input: N = 4, M = 2, K = 2
arr[] = {3, 2, 100, 1};
Output: 106
Explanation: subsets are: (3, 2), (100, 1) 2 subsets of size 2
Aquí podemos ver que necesitamos encontrar M subarreglos, cada uno de tamaño K, entonces,
1. Creamos un arreglo presum, que contiene en cada índice la suma de todos los elementos desde ‘ índice ‘ hasta ‘índice + K’ en el arreglo dado. Y el tamaño de la array de suma será n+1-k .
2. Ahora, si incluimos el subarreglo de tamaño k, entonces no podemos incluir ninguno de los elementos de ese subarreglo nuevamente en ningún otro subarreglo, ya que creará subarreglos superpuestos. Entonces hacemos una llamada recursiva excluyendo los k elementos del subarreglo incluido.
3. Si excluimos un subarreglo, entonces podemos usar los siguientes k-1 elementos de ese subarreglo en otros subarreglos, por lo que haremos una llamada recursiva simplemente excluyendo el primer elemento de ese subarreglo.
4. Por último, devuelva el máximo (suma incluida, suma excluida).
C++
// C++ program to find Max sum of M non-overlapping
// subarray of size K in an Array
#include <bits/stdc++.h>
using namespace std;
// calculating presum of array. presum[i]
// is going to store prefix sum of subarray
// of size k beginning with arr[i]
void calculatePresumArray(int presum[],
int arr[], int n, int k)
{
for (int i=0; i<k; i++)
presum[0] += arr[i];
// store sum of array index i to i+k
// in presum array at index i of it.
for (int i = 1; i <= n - k; i++)
presum[i] += presum[i-1] + arr[i+k-1] -
arr[i-1];
}
// calculating maximum sum of m non overlapping array
int maxSumMnonOverlappingSubarray(int presum[],
int m, int size, int k, int start)
{
// if m is zero then no need any array
// of any size so return 0.
if (m == 0)
return 0;
// if start is greater then the size
// of presum array return 0.
if (start > size - 1)
return 0;
int mx = 0;
// if including subarray of size k
int includeMax = presum[start] +
maxSumMnonOverlappingSubarray(presum,
m - 1, size, k, start + k);
// if excluding element and searching
// in all next possible subarrays
int excludeMax =
maxSumMnonOverlappingSubarray(presum,
m, size, k, start + 1);
// return max
return max(includeMax, excludeMax);
}
// Driver code
int main()
{
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
// resulting presum array will have a size = n+1-k
cout << maxSumMnonOverlappingSubarray(presum,
m, n + 1 - k, k, 0);
return 0;
}
Java
// Java program to find Max sum
// of M non-overlapping subarray
// of size K in an Array
import java.io.*;
class GFG
{
// calculating presum of array.
// presum[i] is going to store
// prefix sum of subarray of
// size k beginning with arr[i]
static void calculatePresumArray(int presum[],
int arr[],
int n, int k)
{
for (int i = 0; i < k; i++)
presum[0] += arr[i];
// store sum of array index i to i+k
// in presum array at index i of it.
for (int i = 1; i <= n - k; i++)
presum[i] += presum[i - 1] + arr[i + k - 1] -
arr[i - 1];
}
// calculating maximum sum of
// m non overlapping array
static int maxSumMnonOverlappingSubarray(int presum[],
int m, int size,
int k, int start)
{
// if m is zero then no need
// any array of any size so
// return 0.
if (m == 0)
return 0;
// if start is greater then the
// size of presum array return 0.
if (start > size - 1)
return 0;
int mx = 0;
// if including subarray of size k
int includeMax = presum[start] +
maxSumMnonOverlappingSubarray(presum,
m - 1, size, k, start + k);
// if excluding element and searching
// in all next possible subarrays
int excludeMax =
maxSumMnonOverlappingSubarray(presum,
m, size, k, start + 1);
// return max
return Math.max(includeMax, excludeMax);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = arr.length;
int m = 3, k = 1;
int presum[] = new int[n + 1 - k] ;
calculatePresumArray(presum, arr, n, k);
// resulting presum array
// will have a size = n+1-k
System.out.println(maxSumMnonOverlappingSubarray(presum,
m, n + 1 - k, k, 0));
}
}
// This code is contributed by anuj_67.
Python
# Python3 program to find Max sum of M non-overlapping # subarray of size K in an Array # calculating presum of array. presum[i] # is going to store prefix sum of subarray # of size k beginning with arr[i] def calculatePresumArray(presum,arr, n, k): for i in range(k): presum[0] += arr[i] # store sum of array index i to i+k # in presum array at index i of it. for i in range(1,n - k + 1): presum[i] += presum[i - 1] + arr[i + k - 1] - arr[i - 1] # calculating maximum sum of m non overlapping array def maxSumMnonOverlappingSubarray(presum, m, size, k, start): # if m is zero then no need any array # of any size so return 0. if (m == 0): return 0 # if start is greater then the size # of presum array return 0. if (start > size - 1): return 0 mx = 0 # if including subarray of size k includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum,m - 1, size, k, start + k) # if excluding element and searching # in all next possible subarrays excludeMax = maxSumMnonOverlappingSubarray(presum,m, size, k, start + 1) # return max return max(includeMax, excludeMax) # Driver code arr = [2, 10, 7, 18, 5, 33, 0] n = len(arr) m, k = 3, 1 presum = [0 for i in range(n + 1 - k)] calculatePresumArray(presum, arr, n, k) # resulting presum array will have a size = n+1-k print(maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0)) # This code is contributed by mohit kumar
C#
// C# program to find Max sum of M
// non-overlapping subarray of size
// K in an Array
using System;
class GFG {
// calculating presum of array.
// presum[i] is going to store
// prefix sum of subarray of
// size k beginning with arr[i]
static void calculatePresumArray(int []presum,
int []arr, int n, int k)
{
for (int i = 0; i < k; i++)
presum[0] += arr[i];
// store sum of array index i to i+k
// in presum array at index i of it.
for (int i = 1; i <= n - k; i++)
presum[i] += presum[i - 1] + arr[i + k - 1]
- arr[i - 1];
}
// calculating maximum sum of
// m non overlapping array
static int maxSumMnonOverlappingSubarray(
int []presum, int m, int size,
int k, int start)
{
// if m is zero then no need
// any array of any size so
// return 0.
if (m == 0)
return 0;
// if start is greater then the
// size of presum array return 0.
if (start > size - 1)
return 0;
//int mx = 0;
// if including subarray of size k
int includeMax = presum[start] +
maxSumMnonOverlappingSubarray(presum,
m - 1, size, k, start + k);
// if excluding element and searching
// in all next possible subarrays
int excludeMax =
maxSumMnonOverlappingSubarray(presum,
m, size, k, start + 1);
// return max
return Math.Max(includeMax, excludeMax);
}
// Driver code
public static void Main ()
{
int []arr = { 2, 10, 7, 18, 5, 33, 0 };
int n = arr.Length;
int m = 3, k = 1;
int []presum = new int[n + 1 - k] ;
calculatePresumArray(presum, arr, n, k);
// resulting presum array
// will have a size = n+1-k
Console.WriteLine(
maxSumMnonOverlappingSubarray(presum,
m, n + 1 - k, k, 0));
}
}
// This code is contributed by anuj_67.
Javascript
<script>
// Javascript program to find Max sum
// of M non-overlapping subarray
// of size K in an Array
// calculating presum of array.
// presum[i] is going to store
// prefix sum of subarray of
// size k beginning with arr[i]
function calculatePresumArray(presum,arr,n,k)
{
for (let i = 0; i < k; i++)
presum[0] += arr[i];
// store sum of array index i to i+k
// in presum array at index i of it.
for (let i = 1; i <= n - k; i++)
presum[i] += presum[i - 1] + arr[i + k - 1] -
arr[i - 1];
}
// calculating maximum sum of
// m non overlapping array
function maxSumMnonOverlappingSubarray(presum,m,size,k,start)
{
// if m is zero then no need
// any array of any size so
// return 0.
if (m == 0)
return 0;
// if start is greater then the
// size of presum array return 0.
if (start > size - 1)
return 0;
let mx = 0;
// if including subarray of size k
let includeMax = presum[start] +
maxSumMnonOverlappingSubarray(presum,
m - 1, size, k, start + k);
// if excluding element and searching
// in all next possible subarrays
let excludeMax =
maxSumMnonOverlappingSubarray(presum,
m, size, k, start + 1);
// return max
return Math.max(includeMax, excludeMax);
}
// Driver code
let arr=[2, 10, 7, 18, 5, 33, 0];
let n = arr.length;
let m = 3, k = 1;
let presum = new Array(n + 1 - k) ;
for(let i = 0; i < presum.length; i++)
{
presum[i] = 0;
}
calculatePresumArray(presum, arr, n, k);
// resulting presum array
// will have a size = n+1-k
document.write(maxSumMnonOverlappingSubarray(presum,
m, n + 1 - k, k, 0));
// This code is contributed by patel2127
</script>
Producción :
61