力扣每日一题3287

题目描述：

看不懂。之能解析为//前半|运算 ^ 后半|运算。官解用的动态规划

官解：

class Solution {
    public int maxValue(int[] nums, int k) {
        List<Set<Integer>> A = findORs(nums, k);
        List<Set<Integer>> B = findORs(reverse(nums), k);
        int mx = 0;
        for (int i = k - 1; i < nums.length - k; i++) {
            for (int a : A.get(i)) {
                for (int b : B.get(nums.length - i - 2)) {
                    mx = Math.max(mx, a ^ b);
                }
            }
        }
        return mx;
    }

    private List<Set<Integer>> findORs(int[] nums, int k) {
        List<Set<Integer>> dp = new ArrayList<>();
        List<Set<Integer>> prev = new ArrayList<>();
        for (int i = 0; i <= k; i++) {
            prev.add(new HashSet<>());
        }
        prev.get(0).add(0);
        for (int i = 0; i < nums.length; i++) {
            for (int j = Math.min(k - 1, i + 1); j >= 0; j--) {
                for (int x : prev.get(j)) {
                    prev.get(j + 1).add(x | nums[i]);
                }
            }
            dp.add(new HashSet<>(prev.get(k)));
        }
        return dp;
    }

    private int[] reverse(int[] nums) {
        int[] reversed = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            reversed[i] = nums[nums.length - 1 - i];
        }
        return reversed;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array/solutions/3037275/qiu-chu-shu-zu-zhong-zui-da-xu-lie-zhi-b-bhnk/
来源：力扣（LeetCode）

找到了一位大佬写的,只能用震撼来形容

或运算性质：

或运算 如果 a|b|c|d = z，e|f = z，那么 (e|f)| a = z， (e|f)| a | b = z,(e|f)| a | b | c = z,(e|f)| a | b | c |d = z 也就是说如果或值z的子数组最短长度为2,最长长度为6，z的子数组可以取到2~6中的任意长度。

class Solution {
    public int maxValue(int[] nums, int k) {
        // 如果k = 1,单独处理
        if (k == 1) {
            int rst = 0;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    rst = Math.max(rst, nums[i] ^ nums[j]);
                }
            }
            return rst;
        }
        // 找到最大的或值
        int maxOr = 0;
        for (int num : nums) {
            maxOr = maxOr | num;
        }
        // 或值在 0~maxOr之间，需要maxSize空间来存放所有或值组合
        int maxSize = maxOr + 1;


        // maxLength[i] 表示得到或值i时，最长可以由几个元素组成
        int[] maxLength = new int[maxSize];
        // maxLength[i] 表示得到或值i时，最短可以由几个元素组成
        int[] minLength = new int[maxSize];
        Arrays.fill(minLength, maxSize);
        /*
          由于或值的递增性质。或值or可以在 minLength[or]~maxLength[or]长度取得
          举例：对于数组1,1,1,1
          minLength[1] = 1,maxLength[1] = 4,
          例子中或值为1的子数组或许有很多种组合，但其长度可以在 1,2,3,4中取得
          —— 意味着，如果minLength[x] <= k  ,maxLength[x] >= k，则可以找到长度为k,或值为1的子数组
        */

        // 缓冲池。防止更新数值时影响条件判断
        int[] maxLengthBuffer = new int[maxSize];
        int[] minLengthBuffer = new int[maxSize];

        // 提前声明临时变量
        int orCurrent;
        // kMinPos[x] 代表： 长度为k，或值为x的子数组，存在于[0,kMinPos[x]]中。
        int[] kMinPos = new int[maxSize];
        // 初始值
        Arrays.fill(kMinPos, nums.length);

        // 找出定义长度为 2 * k 的序列 的左边部分(0~k-1)的所有或值，并得到这些或值的kMinPos
        // 意味着经历循环之后：对于kMinPos[x] < maxSize， 长度为k，或值为x的子数组，存在于[0,kMinPos[x]]中。
        for (int i = 0, len = nums.length - k; i < len; i++) {
            // 填充至buffer
            System.arraycopy(maxLength, 0, maxLengthBuffer, 0, maxSize);
            System.arraycopy(minLength, 0, minLengthBuffer, 0, maxSize);
            // 对于nums[i]，尝试与[0,i-1]的任意子数组结合，并得到新的或值
            for (int orBefore = 0; orBefore < maxLength.length; orBefore++) {
                // 或值orBefore需要多子数组必须小于k，否则加上nums[i]构成的子数组元素数量将大于k,不满足要求
                if (minLength[orBefore] < k) {
                    // 计算结果
                    orCurrent = orBefore | nums[i];
                    // 这个或值在[0,i-1]中没有出现
                    if (maxLength[orCurrent] == 0) {
                        // 动态规划，在i 与[0,i-1]中可能有很多种可能得到此或值，只记录最小长度的可能
                        minLengthBuffer[orCurrent] = Math.min(minLengthBuffer[orCurrent], minLength[orBefore] + 1);
                    }
                    // 在i 与[0,i-1]中可能有很多种可能得到此或值，记录最大长度的可能
                    maxLengthBuffer[orCurrent] = Math.max(maxLengthBuffer[orCurrent], maxLength[orBefore] + 1);
                    // 条件minLength[orBefore] < k，故再加上一个值nums[i]之后，条件minLengthBuffer[orCurrent]<=k,不必再判断
                    // 此时，形成条件minLength[x] <= k  ,maxLength[x] >= k
                    // 故在[0,i]中存在或值为x，长度为k的数组。
                    if (maxLengthBuffer[orCurrent] >= k) {
                        kMinPos[orCurrent] = Math.min(kMinPos[orCurrent], i);
                    }
                }
            }
            // 不或任何值。
            maxLengthBuffer[nums[i]] = Math.max(1, maxLengthBuffer[nums[i]]);
            // 由于或函数的性质，此处最短可以直接取1
            minLengthBuffer[nums[i]] = 1;
            // 将[0,1]的计算结果写入
            System.arraycopy(maxLengthBuffer, 0, maxLength, 0, maxSize);
            System.arraycopy(minLengthBuffer, 0, minLength, 0, maxSize);
        }
        /////////////////////////////////////////////////////////////////////
        int rst = 0;
        // 从右到左再重复一遍
        Arrays.fill(maxLength, 0);
        Arrays.fill(minLength, maxSize);
        // 若长度为k,或值为x的子数组在[i,num.length)中处理过，那么j<i,[i,num.length)中就不必重复处理。
        Set<Integer> visit = new HashSet<>();
        for (int i = nums.length - 1; i >= k; i--) {
            System.arraycopy(maxLength, 0, maxLengthBuffer, 0, maxSize);
            System.arraycopy(minLength, 0, minLengthBuffer, 0, maxSize);
            for (int orBefore = 0; orBefore < maxLength.length; orBefore++) {
                if (minLength[orBefore] < k) {
                    orCurrent = orBefore | nums[i];
                    if (maxLength[orCurrent] == 0) {
                        minLengthBuffer[orCurrent] = Math.min(minLengthBuffer[orCurrent], minLength[orBefore] + 1);
                    }
                    maxLengthBuffer[orCurrent] = Math.max(maxLengthBuffer[orCurrent], maxLength[orBefore] + 1);
                    // 注意这一步与左边时处理的不同，在这里，我们找到了在[i,nums.length)中，存在长度为k,或值为orCurrent的子数组
                    if (maxLengthBuffer[orCurrent] >= k && !visit.contains(orCurrent)) {
                        visit.add(orCurrent);
                        // 我们应该查找[0,i)中所有长度为k的子数组的或值。
                        // 也即是：所有长度为k，或值为orLeft的子数组满足kMinPos[orLeft] < i
                        for (int orLeft = 0; orLeft < kMinPos.length; orLeft++) {
                            if (kMinPos[orLeft] < i) {
                                // 在这一步中，我们以i为分割点，orLeft是由[0,i]中长度为k的子数组计算得来，orCurrent是由(i,nums.length)中长度为k的子数组计算得来
                                rst = Math.max(rst, orLeft ^ orCurrent);
                            }
                        }

                    }
                }
            }
            maxLengthBuffer[nums[i]] = Math.max(1, maxLengthBuffer[nums[i]]);
            minLengthBuffer[nums[i]] = 1;
            System.arraycopy(maxLengthBuffer, 0, maxLength, 0, maxSize);
            System.arraycopy(minLengthBuffer, 0, minLength, 0, maxSize);
        }
        return rst;
    }
}

作者：白衣生雪
链接：https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array/solutions/3050854/dong-gui-wei-yun-suan-by-bai-yi-sheng-xu-5q79/
来源：力扣（LeetCode）