LeetCode 3287 - Find the Maximum Sequence Value of Array

We are given an array nums and an integer k. We must choose a subsequence of exactly 2 k elements while preserving the original order of the array. After selecting the subsequence, we split it into two equal halves: - The first k selected elements form the left group.

leetcodehardarraydynamic-programmingbit-manipulation

LeetCode Problem 3287

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation

Solution

LeetCode 3287 - Find the Maximum Sequence Value of Array

Problem Understanding

We are given an array nums and an integer k. We must choose a subsequence of exactly 2 * k elements while preserving the original order of the array.

After selecting the subsequence, we split it into two equal halves:

  • The first k selected elements form the left group.
  • The next k selected elements form the right group.

The value of the subsequence is:

$$(\text{OR of first } k \text{ elements}) \oplus (\text{OR of last } k \text{ elements})$$

where:

  • OR is the bitwise OR operation.
  • XOR is the bitwise XOR operation.

Our goal is to maximize this value over all valid subsequences of size 2 * k.

The key detail is that the subsequence order matters. If we select indices:

$$i_1 < i_2 < \dots < i_{2k}$$

then the first k selected indices contribute to the left OR, and the remaining k selected indices contribute to the right OR.

Understanding the Constraints

The constraints are:

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

The most important observation is that every number contains at most 7 bits.

Therefore every possible OR result is in the range:

$$0 \dots 127$$

Only 128 distinct OR values can ever exist.

This small OR-state space is the key to the solution. Although there may be exponentially many subsequences, the number of distinct OR values remains tiny.

Important Edge Cases

When k = 1, the problem becomes selecting two elements a and b with a before b, maximizing:

$$a \oplus b$$

This is the smallest nontrivial case.

When many elements are identical, numerous subsequences collapse to the same OR value. An efficient solution should exploit this rather than treating every subsequence separately.

When k = n/2, there is only one possible split size. The algorithm must still correctly compute all feasible left and right OR values.

Another important case occurs when many different subsequences produce the same OR result. Tracking OR states instead of individual subsequences is essential for efficiency.

Approaches

Brute Force

A direct approach would enumerate every subsequence of size 2k.

For each chosen subsequence:

  1. Compute the OR of the first k elements.
  2. Compute the OR of the last k elements.
  3. Compute their XOR.
  4. Track the maximum answer.

This is correct because it explicitly checks every valid subsequence.

Unfortunately, the number of subsequences is:

$$\binom{n}{2k}$$

which is astronomically large when n = 400.

Therefore brute force is completely infeasible.

Key Insight

The crucial observation is that every number is smaller than 128.

Therefore every OR value is also between 0 and 127.

Instead of remembering exactly which elements were chosen, we only need to know:

  • how many elements have been chosen,
  • what OR value they produce.

For each position, we can compute all OR values obtainable by choosing exactly t elements from a prefix.

Similarly, we can compute all OR values obtainable by choosing exactly t elements from a suffix.

Once we know:

  • all OR values achievable by selecting k elements in a prefix,
  • all OR values achievable by selecting k elements in a suffix,

we can try every split position and maximize:

$$\text{leftOR} \oplus \text{rightOR}$$

Since there are only 128 OR states, the dynamic programming remains manageable.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O(\binom{n}{2k} \cdot k)$ $O(2k)$ Enumerates all valid subsequences
Optimal $O(n \cdot k \cdot 128 + n \cdot 128^2)$ $O(n \cdot 128)$ Uses DP on OR states

Algorithm Walkthrough

Step 1: Build prefix DP

Let:

$$\text{pref}[i]$$

store all OR values obtainable by selecting exactly k elements from the prefix ending at index i.

To build this, use DP:

$$dp[t]$$

where dp[t] is the set of OR values obtainable by choosing exactly t elements so far.

Initially:

  • dp[0] = {0}

When processing a number x:

  • For every OR value in dp[t],
  • Add value | x into dp[t+1].

Whenever t = k, record the reachable OR values for the current prefix.

Step 2: Build suffix DP

Perform the same process from right to left.

Let:

$$\text{suff}[i]$$

contain all OR values obtainable by selecting exactly k elements from the suffix starting at index i.

Again use the same OR-state DP.

Step 3: Try every split position

Suppose the first half ends somewhere before index i, and the second half begins at index i.

Then:

  • left OR values come from pref[i-1]
  • right OR values come from suff[i]

Every valid subsequence corresponds to some such split.

Step 4: Compute the best XOR

For every split:

  • iterate through every left OR value,
  • iterate through every right OR value,
  • compute:

$$leftOR \oplus rightOR$$

and update the answer.

Because each side contains at most 128 OR states, this step is cheap.

Why it Works

The DP records exactly all OR values obtainable using a fixed number of selected elements from a prefix or suffix.

For any valid subsequence of size 2k, there exists a unique boundary between its first k chosen elements and last k chosen elements. At that boundary, the left OR appears in the corresponding prefix state and the right OR appears in the corresponding suffix state.

Conversely, any combination of a valid prefix selection and a valid suffix selection represents a legal subsequence whose two halves are separated by the split position.

Therefore examining every split and every reachable OR pair considers all valid solutions, guaranteeing the maximum XOR value is found.

Python Solution

from typing import List

class Solution:
    def maxValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        MAX_OR = 128

        pref = [set() for _ in range(n)]
        dp = [set() for _ in range(k + 1)]
        dp[0].add(0)

        for i, x in enumerate(nums):
            ndp = [s.copy() for s in dp]

            for cnt in range(k):
                for val in dp[cnt]:
                    ndp[cnt + 1].add(val | x)

            dp = ndp
            pref[i] = dp[k].copy()

        suff = [set() for _ in range(n)]
        dp = [set() for _ in range(k + 1)]
        dp[0].add(0)

        for i in range(n - 1, -1, -1):
            x = nums[i]
            ndp = [s.copy() for s in dp]

            for cnt in range(k):
                for val in dp[cnt]:
                    ndp[cnt + 1].add(val | x)

            dp = ndp
            suff[i] = dp[k].copy()

        answer = 0

        for split in range(1, n):
            left_vals = pref[split - 1]
            right_vals = suff[split]

            if not left_vals or not right_vals:
                continue

            for left_or in left_vals:
                for right_or in right_vals:
                    answer = max(answer, left_or ^ right_or)

        return answer

Implementation Explanation

The DP array dp[t] stores all OR values achievable by choosing exactly t elements from the portion processed so far.

For each new number, we create a fresh DP state and either:

  • skip the number,
  • take the number and update the OR value.

After processing index i, dp[k] contains all OR values achievable using exactly k elements from the prefix ending at i. These values are copied into pref[i].

The same logic is repeated from right to left to build suff.

Finally, every possible boundary between the first and second halves is examined. For each boundary, every achievable left OR is paired with every achievable right OR, and the maximum XOR value is updated.

Go Solution

func maxValue(nums []int, k int) int {
	n := len(nums)

	pref := make([]map[int]struct{}, n)

	dp := make([]map[int]struct{}, k+1)
	for i := 0; i <= k; i++ {
		dp[i] = make(map[int]struct{})
	}
	dp[0][0] = struct{}{}

	for i, x := range nums {
		ndp := make([]map[int]struct{}, k+1)

		for j := 0; j <= k; j++ {
			ndp[j] = make(map[int]struct{})
			for v := range dp[j] {
				ndp[j][v] = struct{}{}
			}
		}

		for cnt := 0; cnt < k; cnt++ {
			for v := range dp[cnt] {
				ndp[cnt+1][v|x] = struct{}{}
			}
		}

		dp = ndp

		pref[i] = make(map[int]struct{})
		for v := range dp[k] {
			pref[i][v] = struct{}{}
		}
	}

	suff := make([]map[int]struct{}, n)

	dp = make([]map[int]struct{}, k+1)
	for i := 0; i <= k; i++ {
		dp[i] = make(map[int]struct{})
	}
	dp[0][0] = struct{}{}

	for i := n - 1; i >= 0; i-- {
		x := nums[i]

		ndp := make([]map[int]struct{}, k+1)

		for j := 0; j <= k; j++ {
			ndp[j] = make(map[int]struct{})
			for v := range dp[j] {
				ndp[j][v] = struct{}{}
			}
		}

		for cnt := 0; cnt < k; cnt++ {
			for v := range dp[cnt] {
				ndp[cnt+1][v|x] = struct{}{}
			}
		}

		dp = ndp

		suff[i] = make(map[int]struct{})
		for v := range dp[k] {
			suff[i][v] = struct{}{}
		}
	}

	ans := 0

	for split := 1; split < n; split++ {
		for leftVal := range pref[split-1] {
			for rightVal := range suff[split] {
				if leftVal^rightVal > ans {
					ans = leftVal ^ rightVal
				}
			}
		}
	}

	return ans
}

Go Specific Notes

The Go implementation uses map[int]struct{} as a compact set representation.

Unlike Python's built in set, Go does not provide a native set type, so maps with empty structs are commonly used. Integer overflow is not a concern because all values remain below 128.

Worked Examples

Example 1

Input:

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

Prefix OR states:

Index Reachable OR values using 1 element
0 {2}
1 {2, 6}
2 {2, 6, 7}

Suffix OR states:

Index Reachable OR values using 1 element
2 {7}
1 {6, 7}
0 {2, 6, 7}

Split at position 1:

  • Left = {2}
  • Right = {6,7}

XOR values:

Left Right XOR
2 6 4
2 7 5

Best = 5

Split at position 2:

Left Right XOR
2 7 5
6 7 1

Best remains 5.

Answer:

5

Example 2

Input:

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

Prefix states for exactly two selections:

Index OR Values
0 {}
1 {6}
2 {6,7}
3 {6,7}
4 {6,7}

Suffix states:

Index OR Values
4 {}
3 {7}
2 {7}
1 {7}
0 {7}

The meaningful split is:

left OR = 5 OR 4 = 5
right OR = 6 OR 7 = 7

Result:

5 XOR 7 = 2

Maximum value:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n * k * 128 + n * 128²) At most 128 OR states exist
Space O(n * 128) Stores reachable OR values for every prefix and suffix

The critical observation is that OR values never exceed 127. Therefore each DP layer contains at most 128 distinct states regardless of how many subsequences exist. This transforms an exponential search space into a manageable dynamic programming solution.

Test Cases

sol = Solution()

assert sol.maxValue([2, 6, 7], 1) == 5  # example 1

assert sol.maxValue([4, 2, 5, 6, 7], 2) == 2  # example 2

assert sol.maxValue([1, 2], 1) == 3  # smallest valid n

assert sol.maxValue([7, 7, 7, 7], 2) == 0  # identical numbers

assert sol.maxValue([1, 2, 4, 8], 1) == 12  # maximize XOR with single picks

assert sol.maxValue([127, 127, 127, 127], 2) == 0  # all bits already set

assert sol.maxValue([1, 3, 7, 15, 31, 63], 2) >= 0  # increasing bit coverage

assert sol.maxValue([5, 1, 5, 1, 5, 1], 3) == 0  # only possible split

assert sol.maxValue([1, 2, 3, 4, 5, 6], 2) >= 0  # mixed values

assert sol.maxValue([64, 32, 16, 8, 4, 2, 1], 3) >= 0  # sparse bits

Test Summary

Test Why
[2,6,7], k=1 Official example 1
[4,2,5,6,7], k=2 Official example 2
[1,2], k=1 Smallest valid input
[7,7,7,7], k=2 All values identical
[1,2,4,8], k=1 Simple XOR maximization
[127,127,127,127], k=2 Maximum possible OR value
Increasing powers pattern Expanding OR states
[5,1,5,1,5,1], k=3 Entire array must be chosen
Mixed values General correctness
Sparse bit values Exercises OR combinations

Edge Cases

Case 1: k = 1

This is the smallest selection size. The problem reduces to choosing two elements in order and maximizing their XOR. A common bug is accidentally treating the two halves as unordered groups. The DP correctly preserves the prefix and suffix structure, ensuring order is respected.

Case 2: All Elements Equal

Consider:

[7,7,7,7]

Every OR result is always 7, regardless of which elements are chosen. The answer must therefore be 7 XOR 7 = 0. The DP naturally collapses all equivalent subsequences into a single OR state.

Case 3: k = n/2

When k equals half the array length, the entire subsequence size is exactly n. There may be very few valid choices, sometimes only one. The prefix and suffix DP still work correctly because they enumerate all reachable OR values using exactly k elements on each side of every split.

Case 4: Many Different Subsequences Produce the Same OR

A naive implementation may waste enormous effort distinguishing subsequences that ultimately produce identical OR values. Since OR results are limited to 128 possibilities, the DP stores only distinct OR states. This compression is what makes the algorithm efficient for n = 400.

Case 5: Maximum Bit Coverage

Values can be as large as 127, meaning all seven bits may already be set. Once an OR value reaches 127, adding more numbers cannot increase it. The DP handles this naturally because OR states are stored as distinct values, preventing unnecessary state explosion.