Primer subarreglo que tiene una suma de al menos la mitad de la suma máxima de cualquier subarreglo de tamaño K

Posted on by Rudeus Greyrat

Dado un arreglo arr[] y un entero K , la tarea es encontrar el primer subarreglo que tenga una suma mayor o igual a la mitad de la suma máxima posible de cualquier subarreglo de tamaño K .

Ejemplos:  

Entrada: arr[] = {2, 4, 5, 1, 4, 6, 6, 2, 1, 0}, K = 3 
Salida: 6 2 1 
Explicación: 
La array dada tiene una suma máxima posible de cualquier subarreglo de el tamaño K es 16 del subarreglo {4, 6, 6} . 
Entonces, la suma del subarreglo requerido debe ser mayor o igual a 8 
{6, 2, 1} es el primer subarreglo que tiene una suma de 9 que es mayor que 8.

Entrada: arr[] = {12, 45, 11, 10, 8, 56, 2}, K = 4 
Salida: 45 11 10

Enfoque: este problema se puede resolver utilizando la técnica de ventanas deslizantes porque se deben tener en cuenta los subarreglos. Siga los pasos a continuación para resolver este problema: 

  1. Calcule la suma de todos los subarreglos de tamaño K y guárdelos en un arreglo.
  2. Ahora, encuentra el máximo de todas las sumas.
  3. Iterar sobre la array y encontrar una suma que sea mayor o igual a la mitad de la suma máxima del subarreglo obtenida anteriormente.
  4. Imprima el subarreglo que satisfaga la condición anterior.

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

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Function to print the subarray with sum
// greater or equal than the half of
// the maximum subarray sum of K size
void subArray(int arr[], int n, int k)
{
    int sum = 0;
 
    // Storing sum of first subarray
    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }
 
    // Vector to store the
    // subarray sums
    vector<int> res;
    res.push_back(sum);
 
    // Sliding window technique to
    // Find sum of subarrays of size K
    for (int i = k; i < n; i++) {
        sum -= arr[i - k];
        sum += arr[i];
        res.push_back(sum);
    }
 
    // Maximum sub-array sum
    int max_sum = *max_element(res.begin(),
                               res.end());
 
    int half = max_sum / 2;
 
    // Create a copy vector
    vector<int> copy = res;
 
    // Sort the vector
    sort(copy.begin(),copy.end()); 
   
    int half_index, half_sum;
 
    // Check in a sorted array for
    // an element exceeding
    // half of the max_sum
    for (auto x : copy) {
        if (x >= half) {
            half_sum = x;
            break;
        }
    }
 
    // Calculate index of first
    // subarray having required sum
    for (int x = 0; x < res.size(); x++) {
        if (res[x] == half_sum) {
            half_index = x;
            break;
        }
    }
 
    // Print the subarray
    for (int i = 1; i <= k; i++) {
        cout << arr[half_index + i - 1]
             << " ";
    }
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 4, 5, 1, 4, 6, 6, 2, 1, 0 };
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    subArray(arr, n, k);
 
    return 0;
}
// This code is contributed by akshitdiwan05

Java

// Java implementation of
// the above approach
import java.util.*;
class GFG{
 
// Function to print the subarray with sum
// greater or equal than the half of
// the maximum subarray sum of K size
static void subArray(int arr[],
                     int n, int k)
{
  int sum = 0;
 
  // Storing sum of first subarray
  for (int i = 0; i < k; i++)
  {
    sum += arr[i];
  }
 
  // Vector to store the
  // subarray sums
  Vector<Integer> res = new Vector<>();
  res.add(sum);
 
  // Sliding window technique to
  // Find sum of subarrays of size K
  for (int i = k; i < n; i++)
  {
    sum -= arr[i - k];
    sum += arr[i];
    res.add(sum);
  }
 
  // Maximum sub-array sum
  int max_sum = res.elementAt(0);
  for(int i =0; i < res.size(); i++)
  {
    if(max_sum < res.elementAt(i))
    {
      max_sum = res.elementAt(i);
    }
  }
 
  int half = max_sum / 2;
 
  // Create a copy vector
  Vector<Integer> copy =
                  new Vector<>(res);
 
  // Sort the vector
  Collections.sort(copy);
  int half_index = 0, half_sum = 0;
 
  // Check in a sorted array for
  // an element exceeding
  // half of the max_sum
  for (int x = 0; x < copy.size(); x++)
  {
    if (copy.elementAt(x) >= half)
    {
      half_sum = copy.elementAt(x);
      break;
    }
  }
 
  // Calculate index of first
  // subarray having required sum
  for (int x = 0; x < res.size(); x++)
  {
    if (res.elementAt(x) == half_sum)
    {
      half_index = x;
      break;
    }
  }
 
  // Print the subarray
  for (int i = 1; i <= k; i++)
  {
    System.out.print(
           arr[half_index + i - 1] + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array
  int arr[] = {2, 4, 5, 1, 4,
               6, 6, 2, 1, 0};
  int k = 3;
  int n = arr.length;
 
  // Function Call
  subArray(arr, n, k);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python 3 implementation
# of the above approach
 
# Function to print the
# subarray with sum greater
# or equal than the half of
# the maximum subarray
# sum of K size
def subArray(arr, n, k):
 
    sum = 0
 
    # Storing sum of
    # first subarray
    for i in range (k):
        sum += arr[i]
    
    # Vector to store the
    # subarray sums
    res = []
    res.append(sum)
 
    # Sliding window technique
    # to find sum of subarrays
    # of size K
    for i in range (k, n):
        sum -= arr[i - k]
        sum += arr[i]
        res.append(sum)
    
    # Maximum sub-array sum
    max_sum = max(res)
    half = max_sum // 2
 
    # Create a copy vector
    copy = res.copy()
 
    # Sort the vector
    copy.sort()
  
    # Check in a sorted array for
    # an element exceeding
    # half of the max_sum
    for x in copy:
        if (x >= half):
            half_sum = x
            break
       
    # Calculate index of first
    # subarray having required sum
    for x in range (len(res)):
        if (res[x] == half_sum):
            half_index = x
            break
     
    # Print the subarray
    for i in range (1, k + 1):
        print (arr[half_index + i - 1] ,
               end = " ")
 
# Driver Code
if __name__ == "__main__":
   
    # Given array
    arr = [2, 4, 5, 1, 4,
           6, 6, 2, 1, 0]
    k = 3
    n = len(arr)
 
    # Function Call
    subArray(arr, n, k);
 
# This code is contributed by Chitranayal

C#

// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the subarray with sum
// greater or equal than the half of
// the maximum subarray sum of K size
static void subArray(int []arr,
                     int n, int k)
{
    int sum = 0;
     
    // Storing sum of first subarray
    for(int i = 0; i < k; i++)
    {
        sum += arr[i];
    }
     
    // List to store the
    // subarray sums
    List<int> res = new List<int>();
    res.Add(sum);
     
    // Sliding window technique to
    // Find sum of subarrays of size K
    for(int i = k; i < n; i++)
    {
        sum -= arr[i - k];
        sum += arr[i];
        res.Add(sum);
    }
     
    // Maximum sub-array sum
    int max_sum = res[0];
    for(int i = 0; i < res.Count; i++)
    {
        if (max_sum < res[i])
        {
            max_sum = res[i];
        }
    }
     
    int half = max_sum / 2;
     
    // Create a copy vector
    List<int> copy = new List<int>(res);
     
    // Sort the vector
    copy.Sort();
    int half_index = 0, half_sum = 0;
     
    // Check in a sorted array for
    // an element exceeding
    // half of the max_sum
    for(int x = 0; x < copy.Count; x++)
    {
        if (copy[x] >= half)
        {
            half_sum = copy[x];
            break;
        }
    }
     
    // Calculate index of first
    // subarray having required sum
    for(int x = 0; x < res.Count; x++)
    {
        if (res[x] == half_sum)
        {
            half_index = x;
            break;
        }
    }
     
    // Print the subarray
    for(int i = 1; i <= k; i++)
    {
        Console.Write(
            arr[half_index + i - 1] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 2, 4, 5, 1, 4,
                  6, 6, 2, 1, 0 };
    int k = 3;
    int n = arr.Length;
     
    // Function call
    subArray(arr, n, k);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// javascript implementation of
// the above approach
// Creating the bblSort function
 function bblSort(arr){
      
 for(var i = 0; i < arr.length; i++){
      
   // Last i elements are already in place 
   for(var j = 0; j < ( arr.length - i -1 ); j++){
        
     // Checking if the item at present iteration
     // is greater than the next iteration
     if(arr[j] > arr[j+1]){
          
       // If the condition is true then swap them
       var temp = arr[j]
       arr[j] = arr[j + 1]
       arr[j+1] = temp
     }
   }
 }
 // Print the sorted array
 return arr;
}
    // Function to print the subarray with sum
    // greater or equal than the half of
    // the maximum subarray sum of K size
    function subArray(arr , n , k) {
        var sum = 0;
 
        // Storing sum of first subarray
        for (i = 0; i < k; i++) {
            sum += arr[i];
        }
 
        // Vector to store the
        // subarray sums
        var res =[];
        res.push(sum);
 
        // Sliding window technique to
        // Find sum of subarrays of size K
        for (i = k; i < n; i++) {
            sum -= arr[i - k];
            sum += arr[i];
            res.push(sum);
        }
 
        // Maximum sub-array sum
        var max_sum = res[0];
        for (i = 0; i < res.length; i++) {
            if (max_sum < res[i]) {
                max_sum = res[i];
            }
        }
 
        var half = max_sum / 2;
 
        // Create a copy vector
        var copy = Array(res.length).fill(0);
for (i = 0; i < res.length; i++)
copy[i] = res[i];
        // Sort the vector
        copy = bblSort(copy);
        var half_index = 0, half_sum = 0;
 
        // Check in a sorted array for
        // an element exceeding
        // half of the max_sum
        for (x = 0; x < copy.length; x++) {
            if (copy[x] >= half) {
                half_sum = copy[x];
                break;
            }
        }
 
        // Calculate index of first
        // subarray having required sum
        for (x = 0; x < res.length; x++) {
            if (res[x] == half_sum) {
                half_index = x;
                break;
            }
        }
        // Print the subarray
        for (i = 1; i <= k; i++) {
            document.write(arr[half_index + i - 1] + " ");
        }
    }
 
    // Driver Code
     
        // Given array
        var arr = [ 2, 4, 5, 1, 4, 6, 6, 2, 1, 0 ];
        var k = 3;
        var n = arr.length;
 
        // Function Call
        subArray(arr, n, k);
 
// This code is contributed by todaysgaurav
 
</script>
Producción

6 2 1

Complejidad temporal: O(NlogN) 
Complejidad espacial: O(N) 

Publicación traducida automáticamente

Artículo escrito por akshitdiwan05 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 *