[LC] 3287 Find the Maximum Sequence Value of Array

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array/">Find the Maximum Sequence Value of Array</a>
 * 位运算；数组；动态规划
 */
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;
    }
}

Go

func maxValue(nums []int, k int) int {
    findORs := func(nums []int, k int) []map[int]bool {
        dp := make([]map[int]bool, 0)
        prev := make([]map[int]bool, k+1)
        for i := 0; i <= k; i++ {
            prev[i] = make(map[int]bool)
        }
        prev[0][0] = true

        for i := 0; i < len(nums); i++ {
            for j := min(k-1, i+1); j >= 0; j-- {
                for x := range prev[j] {
                    prev[j+1][x|nums[i]] = true
                }
            }
            current := make(map[int]bool)
            for key := range prev[k] {
                current[key] = true
            }
            dp = append(dp, current)
        }
        return dp
    }

    A := findORs(nums, k)
    reverse(nums)
    B := findORs(nums, k)
    mx := 0

    for i := k - 1; i < len(nums)-k; i++ {
        for a := range A[i] {
            for b := range B[len(nums)-i-2] {
                if a^b > mx {
                    mx = a ^ b
                }
            }
        }
    }
    return mx
}

func reverse(nums []int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}