Largest Permutation

Description:

Given a permutation of first n natural numbers as array and an integer k. Print the lexicographically largest permutation after at most k swaps Input: arr[] = {4, 5, 2, 1, 3} k = 3 Output: 5 4 3 2 1 Explanation: Swap 1st and 2nd elements: 5 4 2 1 3 Swap 3rd and 5th elements: 5 4 3 1 2 Swap 4th and 5th elements: 5 4 3 2 1 Input: arr[] = {2, 1, 3} k = 1 Output: 3 1 2 Test Case 1 Input (stdin) 5 4 5 2 1 3 3 Expected Output 5 4 3 2 1 Test Case 2 Input (stdin) 5 4 5 2 1 3 1 Expected Output 5 4 2 1 3

Program :

#include<iostream>

using namespace std;

int main()

 {

 int i,n,a[50],temp,m;

  cin>>n;

 for(i=0;i<n;i++)

 cin>>a[i];

  cin>>m;

 for(i=0;i<n;i++)

 {

 if(a[i]<a[i+1])

 {

 temp=a[i];

 a[i]=a[i+1];

 a[i+1]=temp;

 }

 if(i==m)

   break;

 }

   for(i=0;i<n;i++)

 {

 if(a[i]<a[i+1])

 {

 temp=a[i];

 a[i]=a[i+1];

 a[i+1]=temp;

 }

   if(i==m)

     break;

   }

 for(i=0;i<n;i++)

 cout<<a[i]<<" ";

 return 0;

 }