JAVA PriorityQueue approach | TC: O(k x logN)
Intuition\nWe\'d always want to flip the smallest element, x. Let\'s assume a number y, where y is greater than x. Flipping y will result in a smaller number th
# Intuition\nWe\'d always want to flip the smallest element, x. Let\'s assume a number y, where y is greater than x. Flipping y will result in a smaller number than flipping x\n- y>x => -y<-x\n\n# Approach\nFrom intuition, it\'s clear that we\'d always need to flip the smallest. We can keep sorting the array everytime we flip a number. But in cases where we need to keep sorting, we can use Priority Queue.\n\n# Complexity\n- Time complexity: O(k x log(N))\n\n- Space complexity: O(N) for PQ.\n\n# Code\n```java []\nclass Solution {\n    public int largestSumAfterKNegations(int[] nums, int k) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>();\n        for(int elem:nums)\n            pq.add(elem);\n\n        for(int i=0; i<k; i++){\n            pq.add(-pq.remove());\n        }\n\n        int sum=0;\n        while(!pq.isEmpty()){\n            sum+=pq.remove();\n        }\n        return sum;\n    }\n}\n```
['Java']