1. Tối ưu hóa tổng mảng sau K lần đổi dấu

Sắp xếp mảng theo giá trị tuyệt đối giảm dần. Duyệt qua mảng, chuyển các số âm thành dương (nếu còn phép đổi). Nếu vẫn còn phép đổi, lặp lại trên phần tử nhỏ nhất.

1. Sắp xếp mảng theo giá trị tuyệt đối giảm dần.
2. Duyệt mảng, đổi dấu các số âm, giảm K mỗi lần đổi.
3. Nếu K còn lớn hơn 0, lặp lại trên phần tử nhỏ nhất cho đến khi hết K.
4. Tính tổng mảng.

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int largestSumAfterKNegations(int[] nums, int K) {
        nums = IntStream.of(nums)
                        .boxed()
                        .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                        .mapToInt(Integer::intValue)
                        .toArray();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && K > 0) {
                nums[i] = -nums[i];
                K--;
            }
        }

        if (K % 2 == 1) {
            nums[nums.length - 1] = -nums[nums.length - 1];
        }

        return Arrays.stream(nums).sum();
    }
}

2. Kiểm tra khả năng hoàn thành vòng tròn trạm xăng

Nếu từ trạm xăng thứ i có thể đi tới trạm xăng thứ j, thì lượng nhiên liệu dư phải không âm.

Giải pháp: Sử dụng phương pháp liệt kê bạo lực và tối ưu hóa.

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;

        for (int i = 0; i < len; ) {
            int j = 0, left = 0;
            while (j < len) {
                int k = (i + j) % len;
                left += gas[k] - cost[k];
                if (left < 0) break;
                j++;
            }

            if (j == len) return i;
            i = i + j + 1;
        }

        return -1;
    }
}

3. Phân phát kẹo cho trẻ em

Mục tiêu là phân phát kẹo sao cho mỗi trẻ em nhận được ít nhất một kẹo và trẻ em có điểm đánh giá cao hơn nhận được nhiều kẹo hơn.

public class Solution {
    public int candy(int[] ratings) {
        int res = 0;
        int len = ratings.length;
        int[] left = new int[len];
        int[] right = new int[len];

        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        }

        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
        }

        for (int i = 0; i < len; i++) {
            res += Math.max(left[i], right[i]) + 1;
        }

        return res;
    }
}