Problem

You are given an integer array nums and a positive integer k.

The value of a sequence seq of size 2 * x is defined as:

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

Return the maximum value of any subsequence of nums having size 2 * k.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: nums = [2,6,7], k = 1

Output: 5

Explanation:

The subsequence `[2, 7]` has the maximum value of `2 XOR 7 = 5`.

Example 2

1
2
3
4
5
6
7
8
9


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

Output: 2

Explanation:

The subsequence `[4, 5, 6, 7]` has the maximum value of `(4 OR 5) XOR (6 OR 7)
= 2`.

Constraints

  • 2 <= nums.length <= 400
  • 1 <= nums[i] < 27
  • 1 <= k <= nums.length / 2

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

We want to select 2*k elements and split them into two groups of size k each, maximizing the value (OR of first group) XOR (OR of second group). Since k is small (up to 8), we can use bitmask DP to try all possible ways to split the selected elements.

Approach

  1. Generate all possible combinations of 2*k elements from nums.
  2. For each such combination, try all possible ways to split it into two groups of size k.
  3. For each split, compute the OR of each group and the XOR of the two results.
  4. Track the maximum value found.
  5. Since k is small, this approach is feasible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int maxSequenceValue(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        function<void(int,vector<int>&)> dfs = [&](int pos, vector<int>& pick) {
            if(pick.size()==2*k) {
                vector<int> mask(2*k);
                for(int m=0;m<(1<<(2*k));++m) if(__builtin_popcount(m)==k) {
                    int a=0,b=0;
                    for(int i=0;i<2*k;++i) {
                        if(m&(1<<i)) a|=nums[pick[i]];
                        else b|=nums[pick[i]];
                    }
                    ans=max(ans,a^b);
                }
                return;
            }
            if(pos==n) return;
            pick.push_back(pos);
            dfs(pos+1,pick);
            pick.pop_back();
            dfs(pos+1,pick);
        };
        vector<int> pick;
        dfs(0,pick);
        return ans;
    }
};
1

// Omitted due to combinatorial explosion for large n, feasible for small k only
1

// Omitted due to combinatorial explosion for large n, feasible for small k only
1

// Omitted due to combinatorial explosion for large n, feasible for small k only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from itertools import combinations
class Solution:
    def maxSequenceValue(self, nums: list[int], k: int) -> int:
        from itertools import combinations
        n = len(nums)
        ans = 0
        for pick in combinations(range(n), 2*k):
            idxs = list(pick)
            for mask in range(1<<(2*k)):
                if bin(mask).count('1') != k:
                    continue
                a = b = 0
                for i in range(2*k):
                    if (mask>>i)&1:
                        a |= nums[idxs[i]]
                    else:
                        b |= nums[idxs[i]]
                ans = max(ans, a^b)
        return ans
1

// Omitted due to combinatorial explosion for large n, feasible for small k only

1

// Omitted due to combinatorial explosion for large n, feasible for small k only

Complexity

  • ⏰ Time complexity: O(C(n,2k) * C(2k,k) * 2k), which is feasible only for small k (k <= 8).
  • 🧺 Space complexity: O(2k), for storing indices and bitmasks