Mayor subarreglo contiguo de tamaño K

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.

Publicación traducida automáticamente

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