文章

[LeetCode] 每日一题 3287. 求出数组中最大序列值

题目链接

https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array

题目描述

给你一个整数数组 nums 和一个  整数 k 。

定义长度为 2 * x 的序列 seq 的  为:

  • (seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]).

请你求出 nums 中所有长度为 2 * k 的子序列最大值 。

子序列 是可以通过从另一个数组删除或不删除某些元素,但不更改其余元素的顺序得到的数组。

示例输入

示例 1

输入:nums = [2,6,7], k = 1

输出:5

解释:

子序列 [2, 7] 的值最大,为 2 XOR 7 = 5 。

示例 2

输入:nums = [4,2,5,6,7], k = 2

输出:2

解释:

子序列 [4, 5, 6, 7] 的值最大,为 (4 OR 5) XOR (6 OR 7) = 2 。

提示

  • 2 <= nums.length <= 400

  • 1 <= nums[i] < 2^7

  • 1 <= k <= nums.length / 2

解题思路

本题的核心思路是通过分割数组,并对每个分割位置计算两个部分的 OR 值,然后通过 XOR 计算得到最大的值

  1. 分割思想:我们可以将 nums 数组分割成两部分,分别计算这两部分的 OR 值,然后对这两个部分的 OR 结果进行 XOR 计算。具体来说,前 k 个元素的 OR 与后 k 个元素的 OR 计算 XOR

  2. 0-1 背包转化:可以通过动态规划(DP)来计算每一部分的 OR 值。我们将问题转化为一个二维的 0-1 背包问题,维度分别为:

    • 选取的元素个数

    • 当前的 OR 值

    我们通过动态规划计算出所有可能的 OR 值,并将前缀部分和后缀部分的 OR 值进行组合,计算它们的 XOR,最终得到最大值

  3. 优化空间:为了节省空间,我们只需要保存当前和前一个状态,而无需保存所有状态。利用这种优化,可以有效降低空间复杂度

代码实现

class Solution {
    public int maxValue(int[] nums, int k) {
        // OR的最大值
        final int MAX_OR_VALUE = 1 << 7;
        int n = nums.length;
        // 后缀部分的 OR 结果
        boolean[][] suffixOR = new boolean[n - k + 1][MAX_OR_VALUE];
        boolean[][] dp = new boolean[k + 1][MAX_OR_VALUE];
        dp[0][0] = true;
        // 计算后缀的 OR 值
        for (int i = n - 1; i >= k; i--) {
            int currentValue = nums[i];
            // 循环更新 dp 数组
            for (int j = Math.min(k - 1, n - 1 - i); j >= 0; j--) {
                for (int x = 0; x < MAX_OR_VALUE; x++) {
                    if (dp[j][x]) {
                        dp[j + 1][x | currentValue] = true;
                    }
                }
            }
            // 将当前的 dp[k] 结果保存到后缀 OR 数组
            if (i <= n - k) {
                suffixOR[i] = dp[k].clone();
            }
        }
        // 存储最大 XOR 值
        int maxXor = 0;
        dp = new boolean[k + 1][MAX_OR_VALUE];
        dp[0][0] = true;

        // 计算前缀的 OR 值并与后缀的结果进行组合计算 XOR
        for (int i = 0; i < n - k; i++) {
            int currentValue = nums[i];
            for (int j = Math.min(k - 1, i); j >= 0; j--) {
                for (int x = 0; x < MAX_OR_VALUE; x++) {
                    if (dp[j][x]) {
                        dp[j + 1][x | currentValue] = true;
                    }
                }
            }
            if (i < k - 1) {
                continue;
            }
            for (int x = 0; x < MAX_OR_VALUE; x++) {
                if (dp[k][x]) {
                    // 与后缀的 OR 值进行 XOR 运算
                    for (int y = 0; y < MAX_OR_VALUE; y++) {
                        if (suffixOR[i + 1][y]) {
                            maxXor = Math.max(maxXor, x ^ y);
                        }
                    }
                }
            }
            // 如果已经得到了理论上的最大值,直接返回
            if (maxXor == MAX_OR_VALUE - 1) {
                return maxXor;
            }
        }
        return maxXor;
    }
}

复杂度分析

  • 时间复杂度:O(nkU + nU^2),其中 nnums 的长度,Unums 所有元素的 OR 值的上界,本题至多为 2^7 - 1。动态规划的部分是 O(nkU),计算 XOR 最大值是 O(nU^2) 的

  • 空间复杂度:O(nU),需要存储动态规划表格和后缀 OR 值

总结

本题通过动态规划和 0-1 背包转化的思想,求解了最大 XOR 值。通过合理的优化和思路的转换,减少了空间复杂度并使得算法更加高效。今天题目较为复杂,一开始没想到思路,最后参考了大佬 灵茶山艾府 的解法 https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array/solutions/2917604/qian-hou-zhui-fen-jie-er-wei-0-1-bei-bao-8icz/

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0