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:
- Calcule la suma de todos los subarreglos de tamaño K y guárdelos en un arreglo.
- Ahora, encuentra el máximo de todas las sumas.
- 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.
- 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