Número máximo formado a partir de una array con un número K de intercambios adyacentes permitidos

Dada una array a[ ] y el número de operaciones de intercambio adyacentes permitidas son K . La tarea es encontrar el número máximo que se puede formar usando estas operaciones de intercambio. 
Ejemplos: 
 

Entrada: a[]={ 1, 2, 9, 8, 1, 4, 9, 9, 9 }, K = 4 
Salida: 9 8 1 2 1 4 9 9 9 
Después del ^primer intercambio, a[ ] se convierte en 1 9 2 8 1 4 9 9 9 
Después del 2 ^o intercambio, a[ ] se convierte en 9 1 2 8 1 4 9 9 9 
Después del 3 ^er intercambio, a[ ] se convierte en 9 1 8 2 1 4 9 9 9 
Después del 4 ^o intercambio, a[ ] se convierte en 9 8 1 2 1 4 9 9 9
Entrada: a[]={2, 5, 8, 7, 9}, K = 2 
Salida: 8 2 5 7 9 

Acercarse: 
 

• Comenzando desde el primer dígito, busque los siguientes K dígitos y almacene el índice del número más grande.
• Lleve el dígito más grande a la parte superior intercambiando los dígitos adyacentes.
• Reducir al valor de K por el número de intercambios adyacentes realizados.
• Repita los pasos anteriores hasta que el número de intercambios sea cero.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the
// elements of the array
void print(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
// Exchange array elements one by
// one from  right to left side
// starting from the current position
// and ending at the target position
void swapMax(int* arr, int target_position,
                      int current_position)
{
    int aux = 0;
    for (int i = current_position;
         i > target_position; i--) {
        aux = arr[i - 1];
        arr[i - 1] = arr[i];
        arr[i] = aux;
    }
}
 
// Function to return the
// maximum number array
void maximizeArray(int* arr,
                   int length, int swaps)
{
    // Base condition
    if (swaps == 0)
        return;
 
    // Start from the first index
    for (int i = 0; i < length; i++) {
        int max_index = 0, max = INT_MIN;
 
        // Search for the next K elements
        int limit = (swaps + i) > length ?
                        length : swaps + i;
 
        // Find index of the maximum
        // element in next K elements
        for (int j = i; j <= limit; j++) {
            if (arr[j] > max) {
                max = arr[j];
                max_index = j;
            }
        }
 
        // Update the value of
        // number of swaps
        swaps -= (max_index - i);
 
        // Update the array elements by
        // swapping adjacent elements
        swapMax(arr, i, max_index);
 
        if (swaps == 0)
            break;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 9, 8, 1, 4, 9, 9, 9 };
    int length = sizeof(arr) / sizeof(int);
    int swaps = 4;
    maximizeArray(arr, length, swaps);
 
    print(arr, length);
 
    return 0;
}

// Java implementation of the above approach
class GFG
{
 
// Function to print the
// elements of the array
static void print(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}
 
// Exchange array elements one by
// one from right to left side
// starting from the current position
// and ending at the target position
static void swapMax(int[] arr, int target_position,
                    int current_position)
{
    int aux = 0;
    for (int i = current_position;
        i > target_position; i--)
    {
        aux = arr[i - 1];
        arr[i - 1] = arr[i];
        arr[i] = aux;
    }
}
 
// Function to return the
// maximum number array
static void maximizeArray(int[] arr,
                int length, int swaps)
{
    // Base condition
    if (swaps == 0)
        return;
 
    // Start from the first index
    for (int i = 0; i < length; i++)
    {
        int max_index = 0, max = Integer.MIN_VALUE;
 
        // Search for the next K elements
        int limit = (swaps + i) > length ?
                        length : swaps + i;
 
        // Find index of the maximum
        // element in next K elements
        for (int j = i; j <= limit; j++)
        {
            if (arr[j] > max)
            {
                max = arr[j];
                max_index = j;
            }
        }
 
        // Update the value of
        // number of swaps
        swaps -= (max_index - i);
 
        // Update the array elements by
        // swapping adjacent elements
        swapMax(arr, i, max_index);
 
        if (swaps == 0)
            break;
    }
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 9, 8, 1, 4, 9, 9, 9 };
    int length = arr.length;
    int swaps = 4;
    maximizeArray(arr, length, swaps);
 
    print(arr, length);
}
}
 
/* This code is contributed by PrinciRaj1992 */

# Python3 implementation of the above approach
import sys
 
# Function to print the
# elements of the array
def print_ele(arr, n) :
     
    for i in range(n) :
        print(arr[i],end=" ");
         
    print();
 
# Exchange array elements one by
# one from right to left side
# starting from the current position
# and ending at the target position
def swapMax(arr, target_position,
                    current_position) :
                         
    aux = 0;
    for i in range(current_position, target_position,-1) :
        aux = arr[i - 1];
        arr[i - 1] = arr[i];
        arr[i] = aux;
 
# Function to return the
# maximum number array
def maximizeArray(arr, length, swaps) :
 
    # Base condition
    if (swaps == 0) :
        return;
 
    # Start from the first index
    for i in range(length) :
        max_index = 0; max = -(sys.maxsize-1);
         
        # Search for the next K elements
        if (swaps + i) > length :
            limit = length
        else:
            limit = swaps + i
             
        # Find index of the maximum
        # element in next K elements
        for j in range(i, limit + 1) :
            if (arr[j] > max) :
                max = arr[j];
                max_index = j;
                 
        # Update the value of
        # number of swaps
        swaps -= (max_index - i);
 
        # Update the array elements by
        # swapping adjacent elements
        swapMax(arr, i, max_index);
 
        if (swaps == 0) :
            break;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 9, 8, 1, 4, 9, 9, 9 ];
    length = len(arr);
    swaps = 4;
    maximizeArray(arr, length, swaps);
 
    print_ele(arr, length);
 
# This code is contributed by AnkitRai01

// C# program to find the sum
// and product of k smallest and
// k largest prime numbers in an array
 
using System;
     
class GFG
{
 
// Function to print the
// elements of the array
static void print(int []arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        Console.Write(arr[i] + " ");
    }
    Console.WriteLine();
}
 
// Exchange array elements one by
// one from right to left side
// starting from the current position
// and ending at the target position
static void swapMax(int[] arr, int target_position,
                    int current_position)
{
    int aux = 0;
    for (int i = current_position;
        i > target_position; i--)
    {
        aux = arr[i - 1];
        arr[i - 1] = arr[i];
        arr[i] = aux;
    }
}
 
// Function to return the
// maximum number array
static void maximizeArray(int[] arr,
                int length, int swaps)
{
    // Base condition
    if (swaps == 0)
        return;
 
    // Start from the first index
    for (int i = 0; i < length; i++)
    {
        int max_index = 0, max = int.MinValue;
 
        // Search for the next K elements
        int limit = (swaps + i) > length ?
                        length : swaps + i;
 
        // Find index of the maximum
        // element in next K elements
        for (int j = i; j <= limit; j++)
        {
            if (arr[j] > max)
            {
                max = arr[j];
                max_index = j;
            }
        }
 
        // Update the value of
        // number of swaps
        swaps -= (max_index - i);
 
        // Update the array elements by
        // swapping adjacent elements
        swapMax(arr, i, max_index);
 
        if (swaps == 0)
            break;
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 9, 8, 1, 4, 9, 9, 9 };
    int length = arr.Length;
    int swaps = 4;
    maximizeArray(arr, length, swaps);
 
    print(arr, length);
}
}
 
/* This code is contributed by PrinciRaj1992 */

<script>
 
// JavaScript implementation of the above approach
 
 
// Function to print the
// elements of the array
function print(arr, n) {
    for (let i = 0; i < n; i++) {
        document.write(arr[i] + " ");
    }
    document.write("<br>");
}
 
// Exchange array elements one by
// one from right to left side
// starting from the current position
// and ending at the target position
function swapMax(arr, target_position, current_position) {
    let aux = 0;
    for (let i = current_position; i > target_position; i--) {
        aux = arr[i - 1];
        arr[i - 1] = arr[i];
        arr[i] = aux;
    }
}
 
// Function to return the
// maximum number array
function maximizeArray(arr, length, swaps) {
    // Base condition
    if (swaps == 0)
        return;
 
    // Start from the first index
    for (let i = 0; i < length; i++) {
        let max_index = 0, max = Number.MIN_SAFE_INTEGER;
 
        // Search for the next K elements
        let limit = (swaps + i) > length ?
            length : swaps + i;
 
        // Find index of the maximum
        // element in next K elements
        for (let j = i; j <= limit; j++) {
            if (arr[j] > max) {
                max = arr[j];
                max_index = j;
            }
        }
 
        // Update the value of
        // number of swaps
        swaps -= (max_index - i);
 
        // Update the array elements by
        // swapping adjacent elements
        swapMax(arr, i, max_index);
 
        if (swaps == 0)
            break;
    }
}
 
// Driver code
 
let arr = [1, 2, 9, 8, 1, 4, 9, 9, 9];
let length = arr.length;
let swaps = 4;
maximizeArray(arr, length, swaps);
 
print(arr, length);
 
// This code is contributed by gfgking
 
</script>

9 8 1 2 1 4 9 9 9

Complejidad de tiempo: O (N * N) donde N es la longitud de la array dada