Java Solutions
Solution 1: Linear Search Approach\n\n- The idea is to replace the minimum element A[minIndex] in array by -A[minIndex] for current operation. In this way we ca
**Solution 1: Linear Search Approach**\n\n- The idea is to replace the minimum element `A[minIndex]` in array by `-A[minIndex]` for current operation. In this way we can make `sum` of array maximum after `K` operations. \n- One interesting case is, once minimum element becomes `0`, we don\u2019t need to make any more changes.\n- Here we use linear search to find minimum element. So the time complexity of the this solution is `O(K * n)`.\n\nTime complexity: `O(K * n)` - where `n` is the length of an input array.\nSpace complexity: `O(1)`\n\n```\nclass Solution\n{\n    public int largestSumAfterKNegations(int[] A, int K)\n    {\n        int sum = 0;\n        \n        while(K-- > 0)\n        {\n            int minIndex = findMinIndex(A);\n\t\t\t\n\t\t\tif(A[minIndex] == 0)\n\t\t\t\tbreak;\n\t\t\telse\n                A[minIndex] = -A[minIndex];\n        }\n        \n        for(int n : A)\n            sum += n;\n        return sum;\n    }\n    \n    private int findMinIndex(int[] A)\n    {\n        int minIndex = 0;\n\n        for(int i = 0; i < A.length; i++)\n        {\n            if(A[i] <= A[minIndex])\n                minIndex = i;\n        }\n        return minIndex;\n    }\n}\n```\n\n**Solution 2: Using minHeap**\n\n- Here an optimized solution is implemented that uses a `PriorityQueue` to find the minimum element quickly.\n- The time complexity to insert `n` elements in to the `PriorityQueue` takes `O(n log n)` time in the general case. An `O(n)` algorithm exists for the special case where the input is already ordered, but this is not provided in `java.util.PriorityQueue` class. Also adding and removing `K` elements from the `minHeap` of size `n` takes `O(K log n)`, so the total complexity is `O(n log n + K log n) = (n + K) * log n`.\n\nTime complexity: `O(n log n + K log n) = (n + K) * log n` - where `n` is the length of an input array.\nSpace complexity: `O(n)` - space required for the `minHeap`\n\n```\nclass Solution\n{\n    public int largestSumAfterKNegations(int[] A, int K)\n    {\n        PriorityQueue<Integer> minHeap = new PriorityQueue<>();\n        int sum = 0;\n        \n        for(int n : A)\n            minHeap.add(n);\n        \n        while(K-- > 0 && minHeap.peek() != 0)\n            minHeap.add(-minHeap.poll());\n        \n        while(!minHeap.isEmpty())\n            sum += minHeap.poll();\n\n        return sum;\n    }\n}\n```
[]