Subarreglo de suma más grande de tamaño K que contiene elementos consecutivos

Dado un arreglo arr[] que consta de N enteros positivos y un entero positivo K , la tarea es encontrar la suma máxima del subarreglo de tamaño K tal que contenga K elementos consecutivos en cualquier combinación.

Ejemplos:

Entrada: arr[] = {10, 12, 9, 8, 10, 15, 1, 3, 2}, K = 3
Salida: 27
Explicación:
El subarreglo que tiene K (= 3) elementos consecutivos es {9, 8, 10} cuya suma de elementos es 9 + 8 + 10 = 27, que es el máximo.

Entrada: arr[] = {7, 20, 2, 3, 4}, K = 2
Salida: 7

Enfoque: el problema dado se puede resolver verificando cada subarreglo de tamaño K si contiene elementos consecutivos o no y luego maximizar la suma del subarreglo en consecuencia. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, diga currSum para almacenar la suma del subarreglo actual de K elementos si los elementos son consecutivos.
  • Inicialice una variable maxSum que almacene la suma resultante máxima de cualquier subarreglo de tamaño K .
  • Iterar sobre el rango [0, N – K] usando la variable i y realizar los siguientes pasos:
    • Almacene los elementos K a partir de i en una array V[] .
    • Ordene la array V[] en orden creciente .
    • Recorra la array V[] para verificar si todos los elementos son consecutivos o no. Si se determina que es cierto, almacene la suma del subarreglo actual en currSum y actualice maxSum al máximo de maxSum y currSum .
  • Después de completar los pasos anteriores, imprima el valor de maxSum 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 find the largest sum
// subarray such that it contains K
// consecutive elements
int maximumSum(vector<int> A, int N,
               int K)
{
    // Stores sum of subarray having
    // K consecutive elements
    int curr_sum = 0;
 
    // Stores the maximum sum among all
    // subarrays of size K having
    // consecutive elements
    int max_sum = INT_MIN;
 
    // Traverse the array
    for (int i = 0; i < N - K + 1; i++) {
 
        // Store K elements of one
        // subarray at a time
        vector<int> dupl_arr(
            A.begin() + i,
            A.begin() + i + K);
 
        // Sort the duplicate array
        // in ascending order
        sort(dupl_arr.begin(),
             dupl_arr.end());
 
        // Checks if elements in subarray
        // are consecutive or not
        bool flag = true;
 
        // Traverse the k elements
        for (int j = 1; j < K; j++) {
 
            // If not consecutive, break
            if (dupl_arr[j]
                    - dupl_arr[j - 1]
                != 1) {
                flag = false;
                break;
            }
        }
 
        // If flag is true update the
        // maximum sum
        if (flag) {
            int temp = 0;
 
            // Stores the sum of elements
            // of the current subarray
            curr_sum = accumulate(
                dupl_arr.begin(),
                dupl_arr.end(), temp);
 
            // Update the max_sum
            max_sum = max(max_sum,
                          curr_sum);
 
            // Reset curr_sum
            curr_sum = 0;
        }
    }
 
    // Return the result
    return max_sum;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 10, 12, 9, 8, 10,
                        15, 1, 3, 2 };
    int K = 3;
    int N = arr.size();
    cout << maximumSum(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.Arrays;
 
class GFG
{
 
    // Function to find the largest sum
    // subarray such that it contains K
    // consecutive elements
public static Integer maximumSum(int[] A, int N, int K)
{
   
    // Stores sum of subarray having
    // K consecutive elements
    int curr_sum = 0;
 
    // Stores the maximum sum among all
    // subarrays of size K having
    // consecutive elements
    int max_sum = Integer.MIN_VALUE;
 
    // Traverse the array
    for (int i = 0; i < N - K + 1; i++) {
 
        // Store K elements of one
        // subarray at a time
        int[] dupl_arr = Arrays.copyOfRange(A, i, i + K);
 
        // Sort the duplicate array
        // in ascending order
        Arrays.sort(dupl_arr);
     
 
        // Checks if elements in subarray
        // are consecutive or not
        Boolean flag = true;
 
        // Traverse the k elements
        for (int j = 1; j < K; j++) {
 
            // If not consecutive, break
            if (dupl_arr[j] - dupl_arr[j - 1]
                != 1) {
                flag = false;
                break;
            }
        }
 
        // If flag is true update the
        // maximum sum
        if (flag) {
            int temp = 0;
 
            // Stores the sum of elements
            // of the current subarray
            curr_sum = 0;
 
            for(int x = 0; x < dupl_arr.length; x++){
                curr_sum += dupl_arr[x];
            }
 
            // Update the max_sum
            max_sum = Math.max(max_sum,
                          curr_sum);
 
            // Reset curr_sum
            curr_sum = 0;
        }
    }
 
    // Return the result
    return max_sum;
}
 
    // Driver Code
public static void main(String args[]) {
        int[] arr = { 10, 12, 9, 8, 10, 15, 1, 3, 2 };
        int K = 3;
        int N = arr.length;
        System.out.println(maximumSum(arr, N, K));
    }
 
}
 
// This code is contributed by _saurabh_jaiswal.

Python3

# Python3 program for the above approach
import sys
 
# Function to find the largest sum
# subarray such that it contains K
# consecutive elements
def maximumSum(A, N, K):
     
    # Stores sum of subarray having
    # K consecutive elements
    curr_sum = 0
 
    # Stores the maximum sum among all
    # subarrays of size K having
    # consecutive elements
    max_sum = -sys.maxsize - 1
 
    # Traverse the array
    for i in range(N - K + 1):
         
        # Store K elements of one
        # subarray at a time
        dupl_arr = A[i:i + K]
 
        # Sort the duplicate array
        # in ascending order
        dupl_arr.sort()
 
        # Checks if elements in subarray
        # are consecutive or not
        flag = True
 
        # Traverse the k elements
        for j in range(1, K, 1):
             
            # If not consecutive, break
            if (dupl_arr[j] - dupl_arr[j - 1] != 1):
                flag = False
                break
 
        # If flag is true update the
        # maximum sum
        if (flag):
            temp = 0
 
            # Stores the sum of elements
            # of the current subarray
            curr_sum = temp
            curr_sum = sum(dupl_arr)
 
            # Update the max_sum
            max_sum = max(max_sum, curr_sum)
 
            # Reset curr_sum
            curr_sum = 0
 
    # Return the result
    return max_sum
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 10, 12, 9, 8, 10,
            15, 1, 3, 2 ]
    K = 3
    N = len(arr)
     
    print(maximumSum(arr, N, K))
     
# This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find the largest sum
// subarray such that it contains K
// consecutive elements
function maximumSum(A, N, K) {
    // Stores sum of subarray having
    // K consecutive elements
    let curr_sum = 0;
 
    // Stores the maximum sum among all
    // subarrays of size K having
    // consecutive elements
    let max_sum = Number.MIN_SAFE_INTEGER;
 
    // Traverse the array
    for (let i = 0; i < N - K + 1; i++) {
 
        // Store K elements of one
        // subarray at a time
        let dupl_arr = [...A.slice(i, i + K)];
 
        // Sort the duplicate array
        // in ascending order
        dupl_arr.sort((a, b) => a - b)
 
        // Checks if elements in subarray
        // are consecutive or not
        let flag = true;
 
        // Traverse the k elements
        for (let j = 1; j < K; j++) {
 
            // If not consecutive, break
            if (dupl_arr[j]
                - dupl_arr[j - 1]
                != 1) {
                flag = false;
                break;
            }
        }
 
        // If flag is true update the
        // maximum sum
        if (flag) {
            let temp = 0;
 
            // Stores the sum of elements
            // of the current subarray
            curr_sum = dupl_arr.reduce((acc, cur) => acc + cur, 0)
 
            // Update the max_sum
            max_sum = Math.max(max_sum,
                curr_sum);
 
            // Reset curr_sum
            curr_sum = 0;
        }
    }
 
    // Return the result
    return max_sum;
}
 
// Driver Code
 
let arr = [10, 12, 9, 8, 10,
    15, 1, 3, 2];
let K = 3;
let N = arr.length;
document.write(maximumSum(arr, N, K));
 
</script>
Producción: 

27

 

Complejidad de tiempo: O(N*K*log K)
Espacio auxiliar: O(K)

Publicación traducida automáticamente

Artículo escrito por supratik_mitra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *