Problem statement

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

The value of a sequence seq of size 2 * x is

(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 of size 2 * k (elements kept in their original order).

Example 1

Input: nums = [2,6,7], k = 1
Output: 5
Explanation: The subsequence [2,7] has value 2 XOR 7 = 5.

Example 2

Input: nums = [4,2,5,6,7], k = 2
Output: 2
Explanation: The subsequence [4,5,6,7] has value (4 OR 5) XOR (6 OR 7) = 5 XOR 7 = 2.

Example 3

Input: nums = [1,2], k = 1
Output: 3
Explanation: The only subsequence of size 2 is the whole array: 1 XOR 2 = 3.

Constraints

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

Hints for Find the Maximum Sequence Value of Array

1. Hint 1

   Every value is below 128, so an OR of any number of them is also below 128 — there are only 128 possible OR results.

2. Hint 2

   Split the array at a position i: the first k chosen elements come from nums[0..i], the last k from nums[i+1..]. For each side you only need the set of ORs that are reachable.

3. Hint 3

   Compute left[i] = set of ORs reachable by picking exactly k elements from the prefix ending at i (a knapsack over count × OR value), right[i] likewise for suffixes, then try every pair across every split.

How to solve Find the Maximum Sequence Value of Array

The two halves are independent once you fix where the first half ends, and the OR of values below 2^7 has only 128 possibilities. So track, for every prefix, which ORs of exactly k chosen elements are reachable — a boolean knapsack — do the same for every suffix, and combine across splits.

Approach

1. Run a DP over the array with can[j][v] = some j elements of the prefix seen so far have OR v; for each element x, for j from k down to 1, set can[j][v | x] whenever can[j - 1][v].
2. After element i, store left[i] = can[k] (a 128-entry set).
3. Run the same DP from the right to get right[i] for the suffix starting at i.
4. For every split i from k - 1 to n - k - 1, and every a in left[i], b in right[i + 1], keep the maximum a XOR b.

Why it works

In any chosen subsequence of size 2k, the k-th chosen index i separates the halves: the first half lies in nums[0..i] and the second in nums[i+1..]. Enumerating every split and every reachable OR on each side therefore covers every subsequence, and every pair counted is realised by some subsequence.

Complexity

• Time — O(n · k · 128 + n · 128^2)
• Space — O(n · 128 + k · 128)

Pitfalls

• Iterate j downwards in the knapsack so an element is not picked twice in one pass.
• Store a copy of can[k] per index; the DP table keeps changing afterwards.
• XOR does not distribute over OR, so you cannot choose the best half greedily — you need the whole set of reachable ORs.

Reference solution

Python

from typing import List

def maxValue(nums: List[int], k: int) -> int:
    n = len(nums)

    def sweep(order):
        can = [[False] * 128 for _ in range(k + 1)]
        can[0][0] = True
        res = [None] * n
        for p in order:
            x = nums[p]
            for j in range(k, 0, -1):
                prev, cur = can[j - 1], can[j]
                for v in range(128):
                    if prev[v]:
                        cur[v | x] = True
            res[p] = [v for v in range(128) if can[k][v]]
        return res

    left = sweep(range(n))
    right = sweep(range(n - 1, -1, -1))
    best = 0
    for i in range(k - 1, n - k):
        for a in left[i]:
            for b in right[i + 1]:
                if a ^ b > best:
                    best = a ^ b
    return best

Java

static boolean[][] sweep(int[] nums, int k, boolean forward) {
    int n = nums.length;
    boolean[][] can = new boolean[k + 1][128];
    can[0][0] = true;
    boolean[][] res = new boolean[n][];
    for (int t = 0; t < n; t++) {
        int p = forward ? t : n - 1 - t;
        int x = nums[p];
        for (int j = k; j >= 1; j--) {
            for (int v = 0; v < 128; v++) if (can[j - 1][v]) can[j][v | x] = true;
        }
        res[p] = can[k].clone();
    }
    return res;
}

public static int maxValue(int[] nums, int k) {
    int n = nums.length;
    boolean[][] left = sweep(nums, k, true);
    boolean[][] right = sweep(nums, k, false);
    int best = 0;
    for (int i = k - 1; i < n - k; i++) {
        for (int a = 0; a < 128; a++) {
            if (!left[i][a]) continue;
            for (int b = 0; b < 128; b++) if (right[i + 1][b]) best = Math.max(best, a ^ b);
        }
    }
    return best;
}

C++

vector<vector<char>> sweepOrs(const vector<int>& nums, int k, bool forward) {
    int n = nums.size();
    vector<vector<char>> can(k + 1, vector<char>(128, 0));
    can[0][0] = 1;
    vector<vector<char>> res(n);
    for (int t = 0; t < n; t++) {
        int p = forward ? t : n - 1 - t;
        int x = nums[p];
        for (int j = k; j >= 1; j--) {
            for (int v = 0; v < 128; v++) if (can[j - 1][v]) can[j][v | x] = 1;
        }
        res[p] = can[k];
    }
    return res;
}

int maxValue(vector<int>& nums, int k) {
    int n = nums.size();
    auto left = sweepOrs(nums, k, true);
    auto right = sweepOrs(nums, k, false);
    int best = 0;
    for (int i = k - 1; i < n - k; i++) {
        for (int a = 0; a < 128; a++) {
            if (!left[i][a]) continue;
            for (int b = 0; b < 128; b++) if (right[i + 1][b]) best = max(best, a ^ b);
        }
    }
    return best;
}

JavaScript

var maxValue = function(nums, k) {
    var n = nums.length;
    var sweep = function(from, to, step) {
        var can = [];
        for (var j = 0; j <= k; j++) can.push(new Array(128).fill(false));
        can[0][0] = true;
        var res = new Array(n);
        for (var p = from; p !== to; p += step) {
            var x = nums[p];
            for (var j = k; j >= 1; j--) {
                var prev = can[j - 1], cur = can[j];
                for (var v = 0; v < 128; v++) if (prev[v]) cur[v | x] = true;
            }
            var list = [];
            for (var v = 0; v < 128; v++) if (can[k][v]) list.push(v);
            res[p] = list;
        }
        return res;
    };
    var left = sweep(0, n, 1);
    var right = sweep(n - 1, -1, -1);
    var best = 0;
    for (var i = k - 1; i < n - k; i++) {
        var A = left[i], B = right[i + 1];
        for (var a = 0; a < A.length; a++) {
            for (var b = 0; b < B.length; b++) if ((A[a] ^ B[b]) > best) best = A[a] ^ B[b];
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard