vadimk772336

Untitled

Sep 23rd, 2021
663
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. void quickSort(int* array, int low, int high)
  4. {
  5.     int i = low;
  6.     int j = high;
  7.     int pivot = array[(i + j) / 2];
  8.     int temp;
  9.  
  10.     while (i <= j) {
  11.         while (array[i] < pivot)
  12.             i++;
  13.         while (array[j] > pivot)
  14.             j--;
  15.         if (i <= j) {
  16.             temp = array[i];
  17.             array[i] = array[j];
  18.             array[j] = temp;
  19.             i++;
  20.             j--;
  21.         }
  22.     }
  23.     if (j > low)
  24.         quickSort(array, low, j);
  25.     if (i < high)
  26.         quickSort(array, i, high);
  27. }
  28.  
  29. int main()
  30. {
  31.     int n, R, L, max_sum, min_sum, curr_sum;
  32.     std::cin >> n;
  33.     int a[n];
  34.  
  35.     for (int i = 0; i < n; i++)
  36.         std::cin >> a[i];
  37.  
  38.     quickSort(a, 0, n);
  39.  
  40.     R = 0;
  41.     max_sum = a[0];
  42.     curr_sum = a[0];
  43.  
  44.     for (L = 0; L < n; L++) {
  45.  
  46.         if (L >= (n - 2)) {
  47.             min_sum = a[L];
  48.         }
  49.         else
  50.             min_sum = a[L] + a[L + 1];
  51.  
  52.         while ((R < (n - 1)) && (a[R + 1] <= min_sum)) {
  53.             R += 1;
  54.             curr_sum += a[R];
  55.         }
  56.  
  57.         if (curr_sum > max_sum)
  58.             max_sum = curr_sum;
  59.  
  60.         curr_sum -= a[L];
  61.     }
  62.  
  63.     std::cout << max_sum;
  64.  
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment