class MaxFinder
{
// finds the max and its index
static int[] findMaxByIteration(int arr[], int start, int end)
{
int max, max_ndx;
max = arr[start];
max_ndx = start;
for (int i=start; i<end; i++)
{
if (arr[i] > max)
{
max = arr[i];
max_ndx = i;
}
}
int result[] = {max, max_ndx};
return result;
}
// optimized to skip iteration, when previous windows max element
// is present in current window
static void optimizedPrintKMax(int arr[], int n, int k)
{
int i, j, max, max_ndx;
// for first window - find by iteration.
int result[] = findMaxByIteration(arr, 0, k);
System.out.printf("%d ", result[0]);
max = result[0];
max_ndx = result[1];
for (j=1; j <= (n-k); j++)
{
// if previous max has fallen out of current window, iterate and find
if (max_ndx < j)
{
result = findMaxByIteration(arr, j, j+k);
max = result[0];
max_ndx = result[1];
}
// optimized path, just compare max with new_elem that has come into the window
else
{
int new_elem_ndx = j + (k-1);
if (arr[new_elem_ndx] > max)
{
max = arr[new_elem_ndx];
max_ndx = new_elem_ndx;
}
}
System.out.printf("%d ", max);
}
}
public static void main(String[] args)
{
int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//int arr[] = {1,5,2,6,3,1,24,7};
int n = arr.length;
int k = 3;
optimizedPrintKMax(arr, n, k);
}
}
задан eyllanesc 13 July 2018 в 11:37
поделиться