題目:

K 次取反后最大化的數(shù)組和

給定一個整數(shù)數(shù)組 A，我們只能用以下方法修改該數(shù)組：我們選擇某個個索引 i 并將 A[i] 替換為 -A[i]，然后總共重復(fù)這個過程 K 次。（我們可以多次選擇同一個索引 i。）

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations

解:

分析例子:

image.png

1.每次找到最小的數(shù)的位置
2.反轉(zhuǎn)最小的數(shù)

實現(xiàn)

package K次反轉(zhuǎn)取最大值;

/**
 * @Description:
 * @Author: kai.yang
 * @Date: 2019-11-02 09:38
 */
public class Test {

    /**
     * 找到最小的index
     */
    public  int getIndexs(int[] datas) {
        int temp = datas[0];
        int index = -1;
        if (datas == null || datas.length == 0) {
            return index;
        }
        for (int i = 0; i < datas.length; i++) {
            if (datas[i] <= temp) {
                temp = datas[i];
                index = i;
            }
        }
        return index;
    }

    /**
     * 反轉(zhuǎn)最小的數(shù)
     * @param datas
     * @param minIndex
     * @return
     */
    public  int[] changeMin(int[] datas, int minIndex) {
        datas[minIndex] = -datas[minIndex];
        return datas;
    }


    /**
     * 求最終和
     * @param datas
     * @param k
     * @return
     */
    public  int sumMax(int[] datas, int k) {
        for (int i = 0; i < k; i++) {
            datas = changeMin(datas, getIndexs(datas));
        }
        int sum = 0;
        for (int i : datas) {
             sum += i;
        }
        return sum;

    }

    public static void main(String[] args) {
        int[] datas = new int[]{1, 2, 3, 4, 5, -1, 4, 3, -9, 4};
        Test test=new Test();
        System.out.println("最終結(jié)果=" + test.sumMax(datas, 6));
    }

}