Thursday, March 21, 2013

Maximum using n moves

Questions Suppose we can compare two arrays like:
{4,2,3} > {3,5,6}
{4,2,3} < {4,3,0}
In each move, you can only switch a number with one of its neighbor.
Given an array and a number n, design an algorithm to make this array maximum using n moves.

Algorithm

1. Find the max number which is at the index <=n+1 in pArray. lets say such number exists at index m where m<=n+1.
2. Swap pArray[m] with pArray[m-1] till m is not equal to 1.
3. n=n-m, pArray++
4. if (n==0) or (pArray == &A[LEN])then exit else go to 1.


public class MaximumUsingNMoves {

public static void MakeMax(int a[], int m)
{
int nCount = m;
for (int i = 0; i < a.length && nCount >= 0; i++)
{
//find the maximum number at right
int nMax = i;
for (int j = i; j < a.length && nCount >= 0 ; j++)
{
nMax = a[j] > a[nMax] ? j : nMax;
nCount--;
}

for (int k = nMax; k != i; k--)
{
int nTmp = a[k];
a[k] = a[k - 1];
a[k - 1] = nTmp;

}
}
}
public static void main(String[] args) {
int a[] = {1,2,3,4,5,6,7,8,9};
MakeMax(a,12);

for (int i = 0; i < a.length; i++)
System.out.print(a[i]+" ");
}
}

No comments: