[JAVA] Simplest explanation and Intuition [ Priority Queue ]
I was having trouble understanding answers from ye15  (link to answer)) and xil899 (link to answer)\n\nSimplest Explanation:\n\nIntuition:\n1. we need Kth large
I was having trouble understanding answers from ye15  ([link to answer](https://leetcode.com/problems/find-the-k-sum-of-an-array/discuss/2456675/Python3-priority-queue))) and xil899 ([link to answer](https://leetcode.com/problems/find-the-k-sum-of-an-array/discuss/2456716/Python3-HeapPriority-Queue-O(NlogN-%2B-klogk)))\n\nSimplest Explanation:\n\nIntuition:\n1. we need Kth largest number -> due to time constraints we cannot check all the possible subsequence sum resulting in O(2 ^ n)\n2. so we need some iterative way that we can run k times to get the answer\n3. generally DP works for these problems but can\'t plug it here\n4. one thing is clear that the maximum and minimum sum can be found by summing all positive numbers or negative numbers respectively. But for this problem we are focusing on maximum sum (**msum**).\n5. once we have the *maximum number* we need the *next maximum number* => this is found by either removing some positive number from the **msum** or adding some negative numbers to the **msum**\n6. we already know that **msum** is only consisting of all of positive numbers but **not** containing negative numbers.\n7. we can achieve the [*either removing some positive number from the msum or adding some negative numbers to the msum*] step by following simple technique:\n\t* create a new array by taking absolute values of numbers in **nums** call it array **A**\n\t* we sort array **A** it by ascending order\n\t* now subtracting the value **A[i]** from **msum** means two things:\n\t\t* if **A[i]** was positive in **nums**, subtracting **A[i]** from **msum** means removing a number from **msum**\n\t\t* if **A[i]** was negative in **nums**, subtracting  **A[i]** from **msum** means adding a negative number to **msum**, eg. if nu**ms[i] == -2** then **A[i] == 2** (now positive), so since msum was not having **-2** value in it(as it only holds positive numbers) thus if we subtract the **A[i]** from msum means : **msum - A[i]** or **msum + nums[i]**\n8. hence if we subtract the **A[0]** value from msum we will get the **next sum** which is <= **msum**\n9. Now to find the subsequent smaller sums, we make use of max heap\n\t* we store the **msum** value and the **index** of element to remove in A into the max heap: **maxH**. Initially this should be **( msum, 0 )** . 0 here is the index of array A that we need to remove from the **msum**.\n\t* if we pop the heap then we should get the next highest sum.\n\n\n```\nclass Solution {\n    public long kSum(int[] A, int k) {\n        PriorityQueue<long[]> maxH = new PriorityQueue<>((a,b) -> (b[0]-a[0])>0?1: (b[0]-a[0]) < 0 ?-1: 0 );\n        \n        // finding the maximum sum -> sum of positive numbers\n        // also making all the numbers in original array as positive\n        long msum = 0;\n        for(int i = 0; i < A.length; i++){\n            msum += A[i]>0?A[i]:0;\n            A[i] = A[i]<0?-A[i]: A[i];\n        }\n        \n        long ans = msum; // this holds the Kth largest number\n        \n        // sorting all the positive numbers in the array A\n        Arrays.sort(A);\n        // System.out.println(Arrays.toString(A));\n        \n        maxH.add(new long[]{msum,0});\n        \n        for(int i = 0; i < k; i++){\n            // get the next maximum sum (cur_sum) and the indexes covered for A array (idx_to_include) for that sum\n            long[] poll = maxH.poll();\n            long cur_sum = poll[0];\n            ans = cur_sum;\n            \n            int idx_to_include = (int)poll[1];\n            \n            // System.out.println(cur_sum+", "+ idx);\n            \n            // remove idx\n            if(idx_to_include < A.length)\n                maxH.add(new long[]{ cur_sum - A[idx_to_include] , idx_to_include+1 });\n            \n            // remove idx and add prev idx\n            if(idx_to_include > 0 && idx_to_include < A.length)\n                maxH.add(new long[]{ cur_sum + A[idx_to_include-1] - A[idx_to_include] , idx_to_include+1 });\n        }\n\n        return ans;\n\n    }\n}\n```\n
['Heap (Priority Queue)', 'Java']