Editorial

Sort the array of diamond sizes. For each index $i$ , consider the sequence $m_{i}, m_{i + 1}, ..., m_{j}$ such that $∣ m_{j} - m_{i} ∣ \leq k$ , but at the same time, $∣ m_{j + 1} - m_{i} ∣ > k$ . Among all such sequences, find the one that contains the largest number of elements.

Example

Sort the sizes of the diamonds.

Consider the interval $[0; 3]$ . The difference between the sizes of the diamonds in this interval does not exceed $k = 3$ . However, Bessie will not be able to showcase all the diamonds in the interval $[0; 4]$ in the barn, since $m_{4} - m_{0} > 3$ .

Algorithm realization

Declare an array to store the sizes of the diamonds.

int m[1000];

Read the input data.

scanf("%d %d", &n, &k);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Sort the array.

sort(m, m + n);

The maximum number of diamonds that Bessie can display in the barn is counted in the variable $res$ .

res = 0;

For each index $i$ , consider the sequence $m_{i}, m_{i + 1}, ..., m_{j}$ of the greatest length such that $∣ m_{j} - m_{i} ∣ \leq k$ . Count the length of this sequence in the variable $c n t$ .

for (i = 0; i < n; i++)
{
  cnt = 0;
  for (j = i; j < n; j++)
  {

As soon as the condition $∣ m_{j} - m_{i} ∣ > k$ becomes true, exit the loop.

    if (m[j] > m[i] + k) break;
    cnt++;
  }

Among the lengths of all sequences, find the maximum.

  if (cnt > res) res = cnt;
}

Print the answer.

printf("%d\n", res);