Maximice la suma de los subarreglos eligiendo M subarreglos de tamaño K

Dada una array arr que contiene N enteros positivos y dos enteros K y M , la tarea es calcular la suma máxima de M subarreglos de tamaño K .

Ejemplo:

Entrada: arr[] = {1, 2, 1, 2, 6, 7, 5, 1}, M = 3, K = 2
Salida: 33
Explicación: Los tres subarreglos elegidos son [2, 6], [6, 7] y [7, 5] respectivamente. Entonces, suma: 8 +12 +13 = 33

Entrada: arr[] = {1, 4, 1, 0, 6, 7, 5, 9}, M = 4, K = 5
Salida: 76

Enfoque: el problema se puede resolver calculando previamente la suma del prefijo hasta cada índice i , que nos dirá la suma del subarreglo de 0 a i . Ahora, este prefijo sum se puede usar para encontrar la suma de cada subarreglo de tamaño K, usando la fórmula:

Suma de subarreglo de i a j = Prefijo suma hasta j – prefijo Suma hasta i

Después de encontrar la suma de todos los subarreglos, elija las M sumas máximas de subarreglos para calcular la respuesta. 
Para resolver este problema, siga los siguientes pasos:

1. Cree un vector prefixSum en el que cada Node represente la suma del prefijo hasta ese índice, y otro vector subarraySum , para almacenar la suma de todos los subarreglos de tamaño K .
2. Ahora, ejecute un ciclo de i=K a i=N y calcule la suma de cada subarreglo usando la fórmula subarraySum[iK, i] = prefixSum[i]-prefixSum[iK] y empújelo en el vector subarraySum .
3. Ordene subarraySum en orden decreciente y agregue los elementos M superiores para obtener la respuesta.
4. Escriba la respuesta de acuerdo con la observación anterior.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the maximum
// sum of M subarrays of size K
int maximumSum(vector<int>& arr, int M, int K)
{
    int N = arr.size();
    vector<int> prefixSum(N + 1, 0);
 
    // Calculating prefix sum
    for (int i = 1; i <= N; ++i) {
        prefixSum[i] = prefixSum[i - 1]
                       + arr[i - 1];
    }
 
    vector<int> subarraysSum;
 
    // Finding sum of each subarray of size K
    for (int i = K; i <= N; i++) {
        subarraysSum.push_back(
            prefixSum[i]
            - prefixSum[i - K]);
    }
 
    sort(subarraysSum.begin(),
         subarraysSum.end(),
         greater<int>());
 
    int sum = 0;
 
    // Selecting the M maximum sums
    // to calculate the answer
    for (int i = 0; i < M; ++i) {
        sum += subarraysSum[i];
    }
    return sum;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 4, 1, 0, 6, 7, 5, 9 };
    int M = 4, K = 5;
    cout << maximumSum(arr, M, K);
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to calculate the maximum
// sum of M subarrays of size K
static  int maximumSum(int []arr, int M, int K)
{
    int N = arr.length;
    int []prefixSum = new int[N + 1];
 
    // Calculating prefix sum
    for (int i = 1; i <= N; ++i) {
        prefixSum[i] = prefixSum[i - 1]
                       + arr[i - 1];
    }
 
    Vector<Integer> subarraysSum = new Vector<Integer>();
 
    // Finding sum of each subarray of size K
    for (int i = K; i <= N; i++) {
        subarraysSum.add(
            prefixSum[i]
            - prefixSum[i - K]);
    }
 
    Collections.sort(subarraysSum,Collections.reverseOrder());
 
    int sum = 0;
 
    // Selecting the M maximum sums
    // to calculate the answer
    for (int i = 0; i < M; ++i) {
        sum += subarraysSum.get(i);
    }
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 4, 1, 0, 6, 7, 5, 9 };
    int M = 4, K = 5;
    System.out.print(maximumSum(arr, M, K));
}
}
 
// This code is contributed by 29AjayKumar

# python program for the above approach
 
# Function to calculate the maximum
# sum of M subarrays of size K
def maximumSum(arr, M, K):
 
    N = len(arr)
    prefixSum = [0 for _ in range(N + 1)]
 
    # Calculating prefix sum
    for i in range(1, N+1):
        prefixSum[i] = prefixSum[i - 1] + arr[i - 1]
 
    subarraysSum = []
 
    # Finding sum of each subarray of size K
    for i in range(K, N+1):
        subarraysSum.append(prefixSum[i] - prefixSum[i - K])
 
    subarraysSum.sort()
    sum = 0
 
    # Selecting the M maximum sums
    # to calculate the answer
    for i in range(0, M):
        sum += subarraysSum[i]
 
    return sum
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 4, 1, 0, 6, 7, 5, 9]
    M = 4
    K = 5
    print(maximumSum(arr, M, K))
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
// Function to calculate the maximum
// sum of M subarrays of size K
static  int maximumSum(int []arr, int M, int K)
{
    int N = arr.Length;
    int []prefixSum = new int[N + 1];
 
    // Calculating prefix sum
    for (int i = 1; i <= N; ++i) {
        prefixSum[i] = prefixSum[i - 1]
                       + arr[i - 1];
    }
     
    List<int> subarraysSum = new List<int>();
 
    // Finding sum of each subarray of size K
    for (int i = K; i <= N; i++) {
        subarraysSum.Add(
            prefixSum[i]
            - prefixSum[i - K]);
    }
     
    subarraysSum.Sort();
    subarraysSum.Reverse();
     
    int sum = 0;
 
    // Selecting the M maximum sums
    // to calculate the answer
    for (int i = 0; i < M; ++i) {
        sum += subarraysSum[i];
    }
    return sum;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 1, 4, 1, 0, 6, 7, 5, 9 };
    int M = 4, K = 5;
    Console.Write(maximumSum(arr, M, K));
}
}
 
// This code is contributed by Samim Hossain Mondal

<script>
// Javascript code for the above approach
  
// Function to calculate the maximum
// sum of M subarrays of size K
function maximumSum(arr, M, K)
{
    var N = arr.length;
    var prefixSum = Array(N + 1).fill(0);
 
    // Calculating prefix sum
    for (var i = 1; i <= N; ++i) {
        prefixSum[i] = prefixSum[i - 1]
                       + arr[i - 1];
    }
    var subarraysSum = [];
    var t = 0;
 
    // Finding sum of each subarray of size K
    for (var i = K; i <= N; i++) {
        subarraysSum[t++] =
            (prefixSum[i] - prefixSum[i - K]);
    }
     
    subarraysSum.sort();
    subarraysSum.reverse();
    var sum = 0;
 
    // Selecting the M maximum sums
    // to calculate the answer
    for (var i = 0; i < M; ++i) {
        sum += subarraysSum[i];
    }
    return sum;
}
 
// Driver Code
var arr = [ 1, 4, 1, 0, 6, 7, 5, 9 ];
var M = 4, K = 5;
document.write(maximumSum(arr, M, K));
 
// This code is contributed by Samim Hossain Mondal
</script>

76

Complejidad temporal:  O(N)
Espacio auxiliar: O(N)