题目

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We may choose the same index i multiple times.)

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: A = [4,2,3], K = 1  Output: 5  Explanation: Choose indices (1,) and A becomes [4,-2,3].

Example 2:

Input: A = [3,-1,0,2], K = 3  Output: 6Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].

Example 3:

Input: A = [2,-3,-1,5,-4], K = 2Output: 13Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].

Note:

1. 1 <= A.length <= 10000
2. 1 <= K <= 10000
3. -100 <= A[i] <= 100

解法一

class Solution {    public int largestSumAfterKNegations(int[] A, int K) {       java.util.Arrays.sort(A);        int lenA = A.length;        int lenB=0,lenC=0;        int result;        if(A[0]>=0){            result = arraySum(A,1,lenA-1);            if(K%2==0)               result+=A[0];            else               result-=A[0];        }else if(A[lenA-1]<=0){            result = arraySum(A,K,lenA-1)-arraySum(A,0,1);        }else{            result=largestSumInBothPlusMinus(A,K);        }               return result;    }    public int largestSumInBothPlusMinus(int[] A, int K) {        int result=0;        int lenA = A.length;         int start = 0;        int end = A.length-1;        int mid=(start+end)/2;        int maxLessIndex=-1;        while(mid>0&&mid+1
    
     =0){                    end=mid-1;                    mid=(start+mid-1)/2;                    if(mid==0){                        maxLessIndex=mid;                        break;                    }                 }else{                    maxLessIndex=mid-1;                    break;                }            }        }        if(K
    

解法二：简化求最大的小于0的值得坐标

class Solution {    public int largestSumAfterKNegations(int[] A, int K) {       java.util.Arrays.sort(A);        int lenA = A.length;        int lenB=0,lenC=0;        int result;        if(A[0]>=0){            result = arraySum(A,1,lenA-1);            if(K%2==0)               result+=A[0];            else               result-=A[0];        }else if(A[lenA-1]<=0){            result = arraySum(A,K,lenA-1)-arraySum(A,0,1);        }else{            result=largestSumInBothPlusMinus(A,K);        }               return result;    }    public int largestSumInBothPlusMinus(int[] A, int K) {        int maxLessIndex=-1;        int result=0;        int lenA=A.length;        int i;        for(i=0;i

解法三：

class Solution {    public int largestSumAfterKNegations(int[] A, int K) {       java.util.Arrays.sort(A);       int count=0;       int sum=0;       int lenA=A.length;       int minNum=A[lenA-1];       for(int i=0;i
    
     K || (K-count)%2==0){           return sum;       }else{           return sum-2*minNum;       }    }}
    

注意：if(A[i]<0 && ++count<=K)这里别写成了++count