maxSumWithRestrictions

#include <vector>
#include <deque>
#include <unordered_map>

using namespace std;

/*
 * Дан непустой массив, нужно найти подотрезок с максимальной суммой.
*/

pair<int, int> solve(const vector<int> &nums) {
    int l = 0, sum = 0, maxsum = nums[0], rOpt = 0;

    for (int r = 0; r < nums.size(); r++) {
        sum += nums[r];
        if (maxsum < sum) {
            rOpt = r;
            maxsum = sum;
        }
        if (sum < 0) {
            sum = 0;
            l = r + 1;
        }
    }

    return make_pair(l, rOpt);
}

vector<int> makePrefixSum(const vector<int> &nums) {
    vector<int> prefs(nums.size() + 1, 0);
    for (int i = 1; i < prefs.size(); i++) {
        prefs[i] = prefs[i - 1] + nums[i - 1];
    }
    return prefs;
}

/*
 * Решение через частичные суммы
 */
pair<int, int> prefixSumSolve(const vector<int> &nums) {
    vector<int> prefs = makePrefixSum(nums);
    int l = 0, maxsum = nums[0], minL = 0, lOpt = 0, rOpt = 0;
    for (int r = 0; r < nums.size(); r++, l++) {
        // для каждого r, ищем минимальный prefs[l], l <= r;
        if (prefs[l] < prefs[minL]) {
            minL = l;
        }
        // оптимальная сумма для данного r.
        int curOptSum = prefs[r + 1] - prefs[minL];
        if (curOptSum > maxsum) {
            maxsum = curOptSum;
            lOpt = minL;
            rOpt = r;
        }
    }

    return make_pair(lOpt, rOpt);
}


struct QueueWithMin {
    deque<int> data;

    void push(int elem) {
        while (!data.empty() && data.back() >= elem) {
            data.pop_back();
        }
        data.push_back(elem);
    }

    void pop(int elem) {
        if (elem == data.front()) {
            data.pop_front();
        }
    }

    int min() {
        return data.front();
    }
};

/*
 * Подотрезок максимальной суммы длины от L до R, содержащий от A до B различных чисел
 */
int maxSumOnRestrictedSegment(const vector<int> &nums, int L, int R, int A, int B) {
    vector<int> prefs = makePrefixSum(nums);
    unordered_map<int, int> countOccurences;
    int countDistinct = 0;
    QueueWithMin searchArea;
    for (int i = 0; i < L - 1; i++) {
        searchArea.push(prefs[i]);
        countOccurences[nums[i]]++;
        if (countOccurences[nums[i]] == 1)
            countDistinct++;
    }
    int maxSum = 0, l = 0;
    for (int r = L - 1; r < nums.size(); r++) {
        searchArea.push(prefs[r]);
        countOccurences[nums[r]]++;
        if (countOccurences[nums[r]] == 1) countDistinct++;
        if (r - l + 1 > R) {
            searchArea.pop(prefs[l]);
            countOccurences[prefs[l]]--;
            if (countOccurences[prefs[l]] == 0) countDistinct--;
            l++;
        }
        int curOptSum = prefs[r + 1] - searchArea.min();
        if (countDistinct <= B && countDistinct >= A && curOptSum > maxSum) {
            maxSum = curOptSum;
        }
    }
    return maxSum;
}