Minimum Difference in Sums After Removal of Elements LeetCode solution in C++

1
class Solution {
2
 public:
3
  long long minimumDifference(vector<int> &nums) {
4
    long long ans = LLONG_MAX, suml = 0, sumr = 0, sumll, sumrr;
5
    int n = nums.size() / 3;
6
    priority_queue<int> lpq;
7
    priority_queue<int, vector<int>, greater<int>> rpq;
8
    for (int i = 0; i < n; i++) {
9
      lpq.push(nums[i]), suml += nums[i];
10
      rpq.push(nums[i + 2 * n]), sumr += nums[i + 2 * n];
11
    }
12
    sumll = suml;
13
    sumrr = sumr;
14
    vector<long long> leftdp(n), rightdp(n);
15
    ans = min(ans, suml - sumr);
16
    for (int i = n; i < 2 * n; i++) {
17
      if (lpq.top() > nums[i]) {
18
        suml -= lpq.top();
19
        suml += nums[i];
20
        lpq.pop();
21
        lpq.push(nums[i]);
22
      }
23
      leftdp[i - n] = suml;
24
    }
25
    for (int i = 2 * n - 1; i >= n; i--) {
26
      if (rpq.top() < nums[i]) {
27
        sumr -= rpq.top();
28
        sumr += nums[i];
29
        rpq.pop();
30
        rpq.push(nums[i]);
31
      }
32
      rightdp[i - n] = sumr;
33
    }
34
    for (int i = 0; i + 1 < n; i++) ans = min(ans, leftdp[i] - rightdp[i + 1]);
35
    ans = min(ans, leftdp[n - 1] - sumrr);
36
    ans = min(ans, sumll - rightdp[0]);
37
    return ans;
38
  }
39
};