Java, 5 lines, beats 100% time & space
\n    public int largestSumAfterKNegations(int[] A, int K) {\n        Arrays.sort( A );\n        for( int i=0, j=0; i<K; i++,A[j]=-A[j] ) if( j+1<A.length && A[
```\n    public int largestSumAfterKNegations(int[] A, int K) {\n        Arrays.sort( A );\n        for( int i=0, j=0; i<K; i++,A[j]=-A[j] ) if( j+1<A.length && A[j+1]<A[j] ) j++;\n        int sum=0;\n        for( int i=0; i<A.length; i++ ) sum+=A[i];\n        return sum;\n    }\n```\nYes, it\'s O(n log n) time, not O(n), but it\'s simple & still pretty fast.  O(1) space, of course.
[]