fieros

maxSumWithRestrictions

Nov 28th, 2021
710
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <deque>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. /*
  8.  * Дан непустой массив, нужно найти подотрезок с максимальной суммой.
  9. */
  10.  
  11. pair<int, int> solve(const vector<int> &nums) {
  12.     int l = 0, sum = 0, maxsum = nums[0], rOpt = 0;
  13.  
  14.     for (int r = 0; r < nums.size(); r++) {
  15.         sum += nums[r];
  16.         if (maxsum < sum) {
  17.             rOpt = r;
  18.             maxsum = sum;
  19.         }
  20.         if (sum < 0) {
  21.             sum = 0;
  22.             l = r + 1;
  23.         }
  24.     }
  25.  
  26.     return make_pair(l, rOpt);
  27. }
  28.  
  29. vector<int> makePrefixSum(const vector<int> &nums) {
  30.     vector<int> prefs(nums.size() + 1, 0);
  31.     for (int i = 1; i < prefs.size(); i++) {
  32.         prefs[i] = prefs[i - 1] + nums[i - 1];
  33.     }
  34.     return prefs;
  35. }
  36.  
  37. /*
  38.  * Решение через частичные суммы
  39.  */
  40. pair<int, int> prefixSumSolve(const vector<int> &nums) {
  41.     vector<int> prefs = makePrefixSum(nums);
  42.     int l = 0, maxsum = nums[0], minL = 0, lOpt = 0, rOpt = 0;
  43.     for (int r = 0; r < nums.size(); r++, l++) {
  44.         // для каждого r, ищем минимальный prefs[l], l <= r;
  45.         if (prefs[l] < prefs[minL]) {
  46.             minL = l;
  47.         }
  48.         // оптимальная сумма для данного r.
  49.         int curOptSum = prefs[r + 1] - prefs[minL];
  50.         if (curOptSum > maxsum) {
  51.             maxsum = curOptSum;
  52.             lOpt = minL;
  53.             rOpt = r;
  54.         }
  55.     }
  56.  
  57.     return make_pair(lOpt, rOpt);
  58. }
  59.  
  60.  
  61. struct QueueWithMin {
  62.     deque<int> data;
  63.  
  64.     void push(int elem) {
  65.         while (!data.empty() && data.back() >= elem) {
  66.             data.pop_back();
  67.         }
  68.         data.push_back(elem);
  69.     }
  70.  
  71.     void pop(int elem) {
  72.         if (elem == data.front()) {
  73.             data.pop_front();
  74.         }
  75.     }
  76.  
  77.     int min() {
  78.         return data.front();
  79.     }
  80. };
  81.  
  82. /*
  83.  * Подотрезок максимальной суммы длины от L до R, содержащий от A до B различных чисел
  84.  */
  85. int maxSumOnRestrictedSegment(const vector<int> &nums, int L, int R, int A, int B) {
  86.     vector<int> prefs = makePrefixSum(nums);
  87.     unordered_map<int, int> countOccurences;
  88.     int countDistinct = 0;
  89.     QueueWithMin searchArea;
  90.     for (int i = 0; i < L - 1; i++) {
  91.         searchArea.push(prefs[i]);
  92.         countOccurences[nums[i]]++;
  93.         if (countOccurences[nums[i]] == 1)
  94.             countDistinct++;
  95.     }
  96.     int maxSum = 0, l = 0;
  97.     for (int r = L - 1; r < nums.size(); r++) {
  98.         searchArea.push(prefs[r]);
  99.         countOccurences[nums[r]]++;
  100.         if (countOccurences[nums[r]] == 1) countDistinct++;
  101.         if (r - l + 1 > R) {
  102.             searchArea.pop(prefs[l]);
  103.             countOccurences[prefs[l]]--;
  104.             if (countOccurences[prefs[l]] == 0) countDistinct--;
  105.             l++;
  106.         }
  107.         int curOptSum = prefs[r + 1] - searchArea.min();
  108.         if (countDistinct <= B && countDistinct >= A && curOptSum > maxSum) {
  109.             maxSum = curOptSum;
  110.         }
  111.     }
  112.     return maxSum;
  113. }
RAW Paste Data