Guest User

Untitled

a guest
Jun 25th, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void bucketSort(int* arr, int n, int k) {
  5. queue<int> q0, q1;
  6. for (int i = 0; i < n; i++) {
  7. if (arr[i] & (1<<k)) {
  8. q1.push(arr[i]);
  9. } else {
  10. q0.push(arr[i]);
  11. }
  12. }
  13. int i = 0;
  14. while (!q0.empty()) {
  15. arr[i] = q0.front();
  16. q0.pop();
  17. i++;
  18. }
  19. while(!q1.empty()) {
  20. arr[i] = q1.front();
  21. q1.pop();
  22. i++;
  23. }
  24. }
  25.  
  26. void radixSort(int* arr, int n) {
  27. for (int i = 0; i < 32; i++) {
  28. bucketSort(arr, n, i);
  29. }
  30. }
  31.  
  32. int maxDiff(int* arr, int n) {
  33. if (n < 2) {
  34. return 0;
  35. }
  36. radixSort(arr, n);
  37. int m = arr[1] - arr[0];
  38. for (int i = 1; i < n-1; i++) {
  39. if (arr[i+1] - arr[i] > m) {
  40. m = arr[i+1] - arr[i];
  41. }
  42. }
  43. return m;
  44. }
  45.  
  46. int main() {
  47. int n;
  48. cin >> n;
  49. int* arr = new int[n];
  50. for (int i = 0; i < n; i++) {
  51. cin >> arr[i];
  52. }
  53. cout << maxDiff(arr, n);
  54. }
Add Comment
Please, Sign In to add comment