Beat 94.56% with explain, O(nlgn)
Sort the array first.\n\nThe negation rules are quite simple\uFF1A\n\n1. execute negation for K times\uFF0Cso use a for loop\n2. after negation, if the next num
Sort the array first.\n\nThe negation rules are quite simple\uFF1A\n\n1. execute negation for K times\uFF0Cso use a for loop\n2. after negation, if the next number (if has) is smaller, the next number is next to negation (if still in for loop). Here we use a greedy strategy. If the next number is non-negative and smaller than the current one, negation it will result in less sum loss(for example current is 4, and next is 1), if the next number is negative and smaller than the current one, negation it will result in more sum (for example current is 4 and next is -3). \n\nAfter that , compute the sum.\n\n    class Solution {\n        public int largestSumAfterKNegations(int[] A, int K) {\n            Arrays.sort(A);\n            int idx = 0;\n            for (int i = 0; i < K; ++i) {\n                A[idx] = -A[idx];\n                if (idx + 1 < A.length) {\n                    if (A[idx + 1] < A[idx]) idx += 1;\n                }\n            }\n            int sum = 0;\n            for (int i = 0; i < A.length; ++i) sum += A[i];\n            return sum;\n        }\n    }\n\n\n
[]