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