fork download
  1. import java.util.*;
  2.  
  3. class Main {
  4. public static void main(String[] args) {
  5. Scanner sc = new Scanner(System.in);
  6.  
  7. int n = sc.nextInt(); // number of elements
  8. int k = sc.nextInt(); // allowed variation
  9. int[] a = new int[n + 1]; // 1-based indexing
  10. int maxVal = 0; // to determine the size of nums[]
  11.  
  12. for (int i = 1; i <= n; i++) {
  13. a[i] = sc.nextInt();
  14. maxVal = Math.max(maxVal, a[i] + k); // max index we need
  15. }
  16.  
  17. // Using array nums as difference array
  18. int[] nums = new int[maxVal + 2]; // extra space for r+1
  19.  
  20. // Build difference array
  21. for (int i = 1; i <= n; i++) {
  22. int l = a[i] - k;
  23. int r = a[i] + k;
  24.  
  25. if (l < 0) l = 0; // to avoid negative index
  26.  
  27. nums[l] += 1;
  28. nums[r + 1] -= 1;
  29. }
  30.  
  31. // Prefix sum to get max overlap
  32. int answer = 0;
  33. for (int i = 0; i <= maxVal + 1; i++) {
  34. if (i > 0) nums[i] += nums[i - 1];
  35. answer = Math.max(answer, nums[i]);
  36. }
  37.  
  38. System.out.println(answer);
  39. }
  40. }
  41.  
Success #stdin #stdout 0.12s 54632KB
stdin
4 1 
3 3 3 5
stdout
4