# 2163. Minimum Difference in Sums After Removal of Elements
###### tags: `Leetcode` `Hard` `Dynamic Programming` `Greedy` `Three Pass`
Link: https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/description/
## 思路
因为删除```n```个元素之后，剩余的```2n```个元素会自然地分成前后两个部分，所以我们很自然地会考察这两个部分的分界点在哪里。假设分界点在位置```k```，那么sum_first怎么选？自然就是```nums[0:k]```里面和最小的```n```个元素；sum_second怎么选？自然就是```nums[k+1:n-1]```里面和最大的```n```个元素。

于是问题转化为，如何高效地在前```k```个元素里找和最小的```n```个元素？显然我们就找最小的```n```个元素即可。从做往右遍历的时候，用一个优先队列始终保存```n```个最小的元素，就可以得到```k```左边最小(包含```k```)的```n```个元素的和，记做```left[k]```。同理我们可以用NlogN的时候，从右往左遍历，得到```rightMax[k]```，表示```k```右边最大(不包含```k```)的```n```个元素的和。

本题的答案就是找一个全局最小的```left[k]-right[k]```
## Code

class Solution {
    public long minimumDifference(int[] nums) {
        int n = nums.length;
        long[] left = new long[n];
        long[] right = new long[n];
        long sum = 0;
        Queue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
        for(int i=0; i<n; i++){
            int num = nums[i];
            pq.add(num);
            sum += num;
            if(pq.size()>n/3){
                sum -= pq.poll();
            }
            left[i] = sum;
        }
        sum = 0;
        pq = new PriorityQueue<>();
        for(int i=n-1; i>=0; i--){
            right[i] = sum;
            int num = nums[i];
            pq.add(num);
            sum += num;
            if(pq.size()>n/3){
                sum -= pq.poll();
            }
        }
        long ans = (long)Double.MAX_VALUE;
        for(int i=n/3-1; i<2*(n/3); i++){
            if(ans>left[i]-right[i]) ans = left[i]-right[i];
        }
        return ans;
    }
}