leetcode->1005. K 次取反后最大化的数组和

迷南。 2022-03-10 07:54 142阅读 0赞

> 给定一个整数数组 A，我们**只能**用以下方法修改该数组：我们选择某个个索引 `i` 并将 `A[i]` 替换为 `-A[i]`，然后总共重复这个过程 `K` 次。（我们可以多次选择同一个索引 `i`。）
> 
> 以这种方式修改数组后，返回数组可能的最大和。

**示例 1：**

>     输入：A = [4,2,3], K = 1
>     输出：5
>     解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

**示例 2：**

>     输入：A = [3,-1,0,2], K = 3
>     输出：6
>     解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

**示例 3：**

>     输入：A = [2,-3,-1,5,-4], K = 2
>     输出：13
>     解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

**提示：**

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

class Solution {
        public int largestSumAfterKNegations(int[] A, int K) {
            if (A == null || A.length == 0) {
                return 0;
            }
            Arrays.sort(A);
            int i = 0;
            // 翻转所有负数
            int count = 0;
            while (count != K && i < A.length && A[i] < 0) {
                A[i] = -A[i];
                i++;
                count++;
            }// 先排序
            Arrays.sort(A);
            // 如果首位是0，则不再进行翻转
            if (A[0] == 0) {
                count = K;
            }// 减去翻转的次数.
            K -= count;
            if (K % 2 == 1) {
                // 最小值变成相反.
                A[0] = -A[0];
            }
            // 求此时数组的和
            return sumArr(A);
        }
    
        private int sumArr(int[] a) {
            int res = 0;
            for (int k : a) {
                res += k;
            }
            return res;
        }
    }