fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void solve(vector<int> nums)
  4. {
  5. 	int n = nums.size();
  6.  
  7.         auto lu = minmax_element(nums.begin(), nums.end());
  8.  
  9.         int l = *lu.first, u = *lu.second;
  10.  
  11.  
  12.  
  13.         int gap = max((u - l) / (n - 1), 1);
  14.         int m = (u - l) / gap + 1;
  15.  
  16.  
  17.         vector<int> bucketsMin(m, INT_MAX);
  18.         vector<int> bucketsMax(m, INT_MIN);
  19.  
  20.         for (int num : nums) 
  21.         {
  22.             int k = (num - l) / gap;
  23.  
  24.  
  25.  
  26.             if (num < bucketsMin[k]) 
  27.                bucketsMin[k] = num;
  28.  
  29.             if (num > bucketsMax[k]) 
  30.                 bucketsMax[k] = num;
  31.         }
  32.  
  33.  
  34.  
  35.  
  36.         int i = 0, j; 
  37.  
  38.         gap = bucketsMax[0] - bucketsMin[0];
  39.         cout<<gap;
  40.         while (i < m) {
  41.             j = i + 1;
  42.             while (j < m && bucketsMin[j] == INT_MAX && bucketsMax[j] == INT_MIN)
  43.                 j++;
  44.             if (j == m) break;
  45.             gap = max(gap, bucketsMin[j] - bucketsMax[i]);
  46.             i = j;
  47.         }
  48.  
  49.        // return gap;
  50. }
  51. int main() 
  52. {
  53. 	vector<int> v={3,6,9,1};
  54. 	solve(v);//<<"\n";
  55.  
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 4304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nSZYcx
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!