Dado un arreglo arr[] de enteros y un entero K , la tarea es encontrar el subarreglo contiguo más grande de tamaño K. Se dice que el subconjunto X es mayor que el subconjunto Y si el primer elemento no coincidente en ambos subconjuntos tiene un valor mayor en X que en Y .
Ejemplos:
Entrada: arr[] = {1, 4, 3, 2, 5}, K = 4
Salida: 4 3 2 5
Dos subarreglos son {1, 4, 3, 2} y {4, 3, 2, 5}.
Por lo tanto, el mayor es {4, 3, 2, 5}Entrada: arr[] = {1, 9, 2, 7, 9, 3}, K = 3
Salida: 9 2 7
Enfoque: genere todos los subconjuntos de tamaño K y almacénelos en cualquier estructura de datos. Ordene todos los subconjuntos y la respuesta será el último subconjunto en la estructura de datos ordenada. En C++, podemos usar un vector de vectores para almacenar subarreglos de tamaño K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the sub-array
vector<int> findSubarray(int a[], int k, int n)
{
// Data-structure to store all
// the sub-arrays of size K
vector<vector<int> > vec;
// Iterate to find all the sub-arrays
for (int i = 0; i < n - k + 1; i++) {
vector<int> temp;
// Store the sub-array elements in the array
for (int j = i; j < i + k; j++) {
temp.push_back(a[j]);
}
// Push the vector in the container
vec.push_back(temp);
}
// Sort the vector of elements
sort(vec.begin(), vec.end());
// The last sub-array in the sorted order
// will be the answer
return vec[vec.size() - 1];
}
// Driver code
int main()
{
int a[] = { 1, 4, 3, 2, 5 };
int k = 4;
int n = sizeof(a) / sizeof(a[0]);
// Get the sub-array
vector<int> ans = findSubarray(a, k, n);
for (auto it : ans)
cout << it << " ";
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG{
// Function that returns the sub-array
static ArrayList<Integer> findSubarray(int a[],
int k, int n)
{
// Data-structure to store all
// the sub-arrays of size K
ArrayList<
ArrayList<Integer>> vec = new ArrayList<
ArrayList<Integer>>();
// Iterate to find all the sub-arrays
for(int i = 0; i < n - k + 1; i++)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
// Store the sub-array elements in the array
for(int j = i; j < i + k; j++)
{
temp.add(a[j]);
}
// Push the vector in the container
vec.add(temp);
}
// Sort the vector of elements
Collections.sort(vec, new Comparator<ArrayList<Integer>>()
{
@Override
public int compare(ArrayList<Integer> o1,
ArrayList<Integer> o2)
{
return o1.get(0).compareTo(o2.get(0));
}
});
// The last sub-array in the sorted order
// will be the answer
return vec.get(vec.size() - 1);
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 4, 3, 2, 5 };
int k = 4;
int n = a.length;
// Get the sub-array
ArrayList<Integer> ans = findSubarray(a, k, n);
for(int it: ans)
{
System.out.print(it + " ");
}
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the approach # Function that returns the sub-array def findSubarray(a, k, n): # Data-structure to store all # the sub-arrays of size K vec=[] # Iterate to find all the sub-arrays for i in range(n-k+1): temp=[] # Store the sub-array elements in the array for j in range(i,i+k): temp.append(a[j]) # Push the vector in the container vec.append(temp) # Sort the vector of elements vec=sorted(vec) # The last sub-array in the sorted order # will be the answer return vec[len(vec) - 1] # Driver code a =[ 1, 4, 3, 2, 5 ] k = 4 n = len(a) # Get the sub-array ans = findSubarray(a, k, n) for it in ans: print(it,end=" ") # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG
{
// Function that returns the sub-array
static List<int> findSubarray(int[] a, int k, int n)
{
// Data-structure to store all
// the sub-arrays of size K
List<List<int>> vec = new List<List<int>>();
// Iterate to find all the sub-arrays
for(int i = 0; i < n - k + 1; i++)
{
List<int> temp = new List<int>();
// Store the sub-array elements in the array
for(int j = i; j < i + k; j++)
{
temp.Add(a[j]);
}
// Push the vector in the container
vec.Add(temp);
}
// Sort the vector of elements
vec.OrderBy( l => l[0]);
// The last sub-array in the sorted order
// will be the answer
return vec[vec.Count - 1];
}
// Driver code
static public void Main (){
int[] a = { 1, 4, 3, 2, 5 };
int k = 4;
int n = a.Length;
// Get the sub-array
List<int> ans = findSubarray(a, k, n);
foreach(int it in ans)
{
Console.Write(it + " ");
}
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation of the approach
// Function that returns the sub-array
function findSubarray(a, k, n)
{
// Data-structure to store all
// the sub-arrays of size K
var vec = [];
// Iterate to find all the sub-arrays
for (var i = 0; i < n - k + 1; i++) {
var temp = [];
// Store the sub-array elements in the array
for (var j = i; j < i + k; j++) {
temp.push(a[j]);
}
// Push the vector in the container
vec.push(temp);
}
// Sort the vector of elements
vec.sort()
// The last sub-array in the sorted order
// will be the answer
return vec[vec.length - 1];
}
// Driver code
var a = [1, 4, 3, 2, 5];
var k = 4;
var n = a.length;
// Get the sub-array
var ans = findSubarray(a, k, n);
ans.forEach(it => {
document.write(it+ " ")
});
// This code is contributed by noob2000.
</script>
Producción:
4 3 2 5
Complejidad de tiempo: O(n*n), ya que se utilizan bucles anidados.
Espacio auxiliar: O(n), ya que se utiliza espacio extra de tamaño n para hacer vector y vector de vectores.