1005. Maximize Sum Of Array After K Negations

#### QUESTION:

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: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
``````

Example 3:

``````Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: 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`

#### EXPLANATION:

1.首先肯定是需要将所有的负数转正数，从最小的负数开始

2.如果负数的个数大于k，那么说明已经尽力了

3.如果负数的个数小于k，那么说明还需要进行正数的转换，那么也是转换最小的值。

#### SOLUTION:

``````class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
Arrays.sort(A);
int index = 0;
while (index<A.length && K>0){
if(A[index]<0) {
A[index] = Math.abs(A[index]);
K--;
index++;
}else break;
}
if(K==0) return IntStream.of(A).sum();
Arrays.sort(A);
int time = K%2;
if(time==1) A[0] = -A[0];
return IntStream.of(A).sum();
}
}

class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
PriorityQueue<Integer> p=new PriorityQueue<Integer>();
int totalSum=0;
for(int a:A)
{
totalSum+=a;
}

for(int i=0;i<K&&!p.isEmpty();i++)
{
int t=p.poll();
totalSum-=t;
totalSum+=-t;