Maximize Sum Of Array After K Negations
给一个数组， 问如何翻转k（求负）个数后，数组和最大。 明显翻转最小的数是最大的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public int largestSumAfterKNegations(int[] A, int K) { for(int i = 0 ; i < K; i++) { int index = findMin(A); A[index] = -A[index]; // always flip min value } int sum = 0; for(int a : A) { sum += a; } return sum; } private int findMin(int[] A) { // return the min index of array int min = Integer.MAX_VALUE; int min_index = -1; for(int i = 0 ; i < A.length; i++) { if(A[i] < min) { min_index = i; min = A[i]; } } return min_index; } } |