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 – Naive Brute Force

Intuition

The simplest way is to try every possible subsequence of length 2 * k (keeping original order), compute the bitwise OR of the first k elements and the OR of the last k elements, then take the XOR of those two ORs. Because k is small and n is at most 400, this brute-force enumerative approach is easy to implement and straightforward to reason about.

Approach

  1. Enumerate all combinations of 2 * k indices from 0..n-1 in increasing order (these represent subsequences and preserve the original order).
  2. For each chosen index tuple idxs of size 2 * k, compute left_or = nums[idxs[0]] | nums[idxs[1]] | ... | nums[idxs[k-1]] and right_or = nums[idxs[k]] | ... | nums[idxs[2*k-1]].
  3. Compute value = left_or ^ right_or and track the maximum over all choices.
  4. Return the maximum value after trying all combinations.

This method is intentionally straightforward and serves as a correctness baseline; it does no advanced pruning or DP.

Complexity

  • ⏰ Time complexity: O(C(n, 2*k) * k) – We enumerate every combination of 2*k indices (there are C(n,2k) of them) and for each we do O(k) work to compute the two ORs.
  • 🧺 Space complexity: O(2*k) – We store the current combination of indices and a few scalars while computing ORs.

Method 2 – Memoized (Prefix/Suffix DP)

Intuition

We can avoid enumerating all C(n,2k) subsequences by precomputing, for every prefix and every possible OR value, whether it’s possible to pick exactly t elements from that prefix that produce that OR. Do the same for suffixes (or equivalently reverse the array and compute the same DP). Then, for each split point between prefix and suffix (i.e., choose how many original elements belong to the prefix), combine possible left OR values (from prefix DP) with possible right OR values (from suffix DP) and maximize their XOR. This trades combinatorial enumeration for DP over the OR-value space, which is small (W = 128) because numbers are small (<= 127).

Approach

  1. Let W be the number of possible OR-values (we use W = 128 since nums[i] < 128).
  2. Build dp_prefix[i][t] = set of OR-values achievable by picking exactly t elements from the first i elements of nums (0 <= i <= n).
  3. Build dp_suffix by reversing nums and computing the same DP; dp_suffix[s][t] then represents achievable ORs using t elements from the last s elements of the original array.
  4. For every split i where the prefix uses the first i elements and the suffix uses the last n - i elements, check all or1 in dp_prefix[i][k] and or2 in dp_suffix[n - i][k] and update answer with or1 ^ or2.
  5. Return the maximum XOR found.

This DP is efficient because W is small (128), so iterating over OR-values is cheap. We use sets for OR-values in languages where convenient and boolean 3D arrays where sets are less convenient.

State Definition

  • dp_prefix[i][t] — the set (or boolean mask) of OR-values reachable by selecting exactly t elements from the prefix of length i.

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
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
  int maxValue(vector<int>& nums, int k) {
    int n = nums.size();
    const int W = 128;  // possible OR values: 0..127

    auto build = [&](const vector<int>& a) {
      int m = a.size();
      // dp[i][t][v] : using first i elements, can we pick t elements with OR == v?
      vector<vector<vector<char>>> dp(m + 1, vector<vector<char>>(k + 1, vector<char>(W, 0)));
      dp[0][0][0] = 1;
      for (int i = 0; i < m; ++i) {
        for (int t = 0; t <= k; ++t) {
          for (int v = 0; v < W; ++v) {
            if (!dp[i][t][v]) continue;
            // not take
            dp[i + 1][t][v] = 1;
            // take
            if (t < k) dp[i + 1][t + 1][v | a[i]] = 1;
          }
        }
      }
      return dp;
    };

    auto dp1 = build(nums);
    reverse(nums.begin(), nums.end());
    auto dp2 = build(nums); // dp2 on reversed array

    int ans = 0;
    for (int i = k; i <= n - k; ++i) {
      for (int v1 = 0; v1 < W; ++v1) {
        if (!dp1[i][k][v1]) continue;
        for (int v2 = 0; v2 < W; ++v2) {
          if (!dp2[n - i][k][v2]) continue;
          ans = max(ans, v1 ^ v2);
        }
      }
    }
    return ans;
  }
};
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

package main

// Helper: compute dp_prefix as slice of slice of maps
func buildDP(a []int, k int) [][][]bool {
  m := len(a)
  W := 128
  dp := make([][][]bool, m+1)
  for i := 0; i <= m; i++ {
    dp[i] = make([][]bool, k+1)
    for t := 0; t <= k; t++ {
      dp[i][t] = make([]bool, W)
    }
  }
  dp[0][0][0] = true
  for i := 0; i < m; i++ {
    for t := 0; t <= k; t++ {
      for v := 0; v < W; v++ {
        if !dp[i][t][v] {
          continue
        }
        dp[i+1][t][v] = true
        if t < k {
          dp[i+1][t+1][v | a[i]] = true
        }
      }
    }
  }
  return dp
}

func maxValue(nums []int, k int) int {
  n := len(nums)
  dp1 := buildDP(nums, k)
  // reverse
  for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
    nums[i], nums[j] = nums[j], nums[i]
  }
  dp2 := buildDP(nums, k)
  W := 128
  ans := 0
  for i := k; i <= n-k; i++ {
    for v1 := 0; v1 < W; v1++ {
      if !dp1[i][k][v1] {
        continue
      }
      for v2 := 0; v2 < W; v2++ {
        if !dp2[n-i][k][v2] {
          continue
        }
        x := v1 ^ v2
        if x > ans {
          ans = x
        }
      }
    }
  }
  return ans
}
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import java.util.*;

class Solution {
  public int maxValue(int[] nums, int k) {
    int n = nums.length;
    final int W = 128;

    boolean[][][] dp1 = buildDP(nums, k, W);
    // reverse array for suffix DP
    reverse(nums);
    boolean[][][] dp2 = buildDP(nums, k, W);

    int ans = 0;
    for (int i = k; i <= n - k; ++i) {
      for (int v1 = 0; v1 < W; ++v1) {
        if (!dp1[i][k][v1]) continue;
        for (int v2 = 0; v2 < W; ++v2) {
          if (!dp2[n - i][k][v2]) continue;
          ans = Math.max(ans, v1 ^ v2);
        }
      }
    }
    return ans;
  }

  private boolean[][][] buildDP(int[] a, int k, int W) {
    int m = a.length;
    boolean[][][] dp = new boolean[m + 1][k + 1][W];
    dp[0][0][0] = true;
    for (int i = 0; i < m; ++i) {
      for (int t = 0; t <= k; ++t) {
        for (int v = 0; v < W; ++v) {
          if (!dp[i][t][v]) continue;
          dp[i + 1][t][v] = true;
          if (t < k) dp[i + 1][t + 1][v | a[i]] = true;
        }
      }
    }
    return dp;
  }

  private void reverse(int[] a) {
    int i = 0, j = a.length - 1;
    while (i < j) {
      int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
      i++; j--;
    }
  }
}
 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
31
32
33
34
35
36
37
38

class Solution {
  fun maxValue(nums: IntArray, k: Int): Int {
    val n = nums.size
    val W = 128

    val dp1 = buildDP(nums.copyOf(), k, W)
    nums.reverse()
    val dp2 = buildDP(nums, k, W)

    var ans = 0
    for (i in k..n - k) {
      for (v1 in 0 until W) {
        if (!dp1[i][k][v1]) continue
        for (v2 in 0 until W) {
          if (!dp2[n - i][k][v2]) continue
          ans = maxOf(ans, v1 xor v2)
        }
      }
    }
    return ans
  }

  private fun buildDP(a: IntArray, k: Int, W: Int): Array<Array<BooleanArray>> {
    val m = a.size
    val dp = Array(m + 1) { Array(k + 1) { BooleanArray(W) } }
    dp[0][0][0] = true
    for (i in 0 until m) {
      for (t in 0..k) {
        for (v in 0 until W) {
          if (!dp[i][t][v]) continue
          dp[i + 1][t][v] = true
          if (t < k) dp[i + 1][t + 1][v or a[i]] = true
        }
      }
    }
    return dp
  }
}
 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
31
32
33
34

from typing import List

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

    def build(a: List[int]):
      m = len(a)
      # dp[i][t] = set of OR-values possible using first i elements picking t elements
      dp = [ [set() for _ in range(k+1)] for _ in range(m+1) ]
      dp[0][0].add(0)
      for i in range(m):
        for t in range(k+1):
          for v in dp[i][t]:
            dp[i+1][t].add(v)
            if t < k:
              dp[i+1][t+1].add(v | a[i])
      return dp

    dp1 = build(nums)
    nums.reverse()
    dp2 = build(nums)

    ans = 0
    for i in range(k, n - k + 1):
      left_set = dp1[i][k]
      right_set = dp2[n - i][k]
      if not left_set or not right_set:
        continue
      for v1 in left_set:
        for v2 in right_set:
          ans = max(ans, v1 ^ v2)
    return ans
 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
31
32
33
34
35
36
37
38
39
40
41
42
43

impl Solution {
  pub fn max_value(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    let w = 128usize;

    fn build(a: &Vec<i32>, k: usize, w: usize) -> Vec<Vec<Vec<u8>>> {
      let m = a.len();
      let mut dp = vec![vec![vec![0u8; w]; k+1]; m+1];
      dp[0][0][0] = 1;
      for i in 0..m {
        for t in 0..=k {
          for v in 0..w {
            if dp[i][t][v] == 0 { continue; }
            dp[i+1][t][v] = 1;
            if t < k {
              let nv = v | (a[i] as usize);
              dp[i+1][t+1][nv] = 1;
            }
          }
        }
      }
      dp
    }

    let mut a = nums.clone();
    let dp1 = build(&a, k, w);
    a.reverse();
    let dp2 = build(&a, k, w);

    let mut ans = 0i32;
    for i in k..=n - k {
      for v1 in 0..w {
        if dp1[i][k][v1] == 0 { continue; }
        for v2 in 0..w {
          if dp2[n - i][k][v2] == 0 { continue; }
          ans = ans.max((v1 ^ v2) as i32);
        }
      }
    }
    ans
  }
}
 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
31
32
33
34
35
36
37
38
39
40

function maxValue(nums: number[], k: number): number {
  const n = nums.length;
  const W = 128;

  function build(a: number[]) {
    const m = a.length;
    const dp: boolean[][][] = new Array(m+1);
    for (let i = 0; i <= m; ++i) {
      dp[i] = new Array(k+1);
      for (let t = 0; t <= k; ++t) dp[i][t] = new Array(W).fill(false);
    }
    dp[0][0][0] = true;
    for (let i = 0; i < m; ++i) {
      for (let t = 0; t <= k; ++t) {
        for (let v = 0; v < W; ++v) {
          if (!dp[i][t][v]) continue;
          dp[i+1][t][v] = true;
          if (t < k) dp[i+1][t+1][v | a[i]] = true;
        }
      }
    }
    return dp;
  }

  const dp1 = build(nums.slice());
  nums.reverse();
  const dp2 = build(nums.slice());

  let ans = 0;
  for (let i = k; i <= n - k; ++i) {
    for (let v1 = 0; v1 < W; ++v1) {
      if (!dp1[i][k][v1]) continue;
      for (let v2 = 0; v2 < W; ++v2) {
        if (!dp2[n - i][k][v2]) continue;
        ans = Math.max(ans, v1 ^ v2);
      }
    }
  }
  return ans;
}

Complexity

  • ⏰ Time complexity: O(n * k * W + n * W^2) – Building the prefix/suffix DP costs O(n * k * W) and combining prefix/suffix OR-values costs O(n * W^2) where W is the OR-value range (here W = 128).
  • 🧺 Space complexity: O(n * k * W) – The prefix and suffix DP tables each store O(n * k * W) boolean states.

Method 3 – Bottom-up DP (Iterative, with rolling updates)

Intuition

The bottom-up DP implements the same reachable-OR idea as Method 2 but builds the DP iteratively from left to right (prefixes) and right to left (suffixes). By using iterative updates (rolling from i to i+1) we make the transition explicit and can optionally optimize memory when full per-index snapshots are not required.

Approach

  1. Initialize dp_prefix[0][0] = {0} (only OR 0 with 0 picks). Iteratively compute dp_prefix[i+1] from dp_prefix[i] by adding the option to take or skip nums[i].
  2. Similarly compute dp_suffix by iterating from the end of the array backward.
  3. Store for each prefix-length i the boolean mask dp_prefix[i][t][v] indicating if OR v is achievable with t picks. Do the same for suffixes.
  4. Combine prefix and suffix OR-values for each valid split i (where i elements are available to the left and n-i to the right) and maximize v1 ^ v2 over all v1 in dp_prefix[i][k] and v2 in dp_suffix[n-i][k].

This method is equivalent in semantics to Method 2 but written as an explicit iterative DP. It also makes it straightforward to replace the full dp_prefix array with a rolling window if you only need the previous state.

State Definition

  • dp_prefix[i][t][v] — boolean reachable state: using first i elements, can we pick exactly t elements with combined OR equal to v.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
public:
  int maxValue(vector<int>& nums, int k) {
    int n = nums.size();
    const int W = 128;

    // build prefix DP iteratively
    vector<vector<vector<char>>> dp_pref(n + 1, vector<vector<char>>(k + 1, vector<char>(W, 0)));
    dp_pref[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int t = 0; t <= k; ++t) {
        for (int v = 0; v < W; ++v) {
          if (!dp_pref[i][t][v]) continue;
          // skip nums[i]
          dp_pref[i+1][t][v] = 1;
          // take nums[i]
          if (t < k) dp_pref[i+1][t+1][v | nums[i]] = 1;
        }
      }
    }

    // build suffix DP iteratively from right to left
    vector<vector<vector<char>>> dp_suf(n + 1, vector<vector<char>>(k + 1, vector<char>(W, 0)));
    dp_suf[0][0][0] = 1;
    for (int i = n-1; i >= 0; --i) {
      int idx = n - 1 - i; // number of elements processed in suffix so far
      for (int t = 0; t <= k; ++t) {
        for (int v = 0; v < W; ++v) {
          if (!dp_suf[idx][t][v]) continue;
          // skip nums[i]
          dp_suf[idx+1][t][v] = 1;
          // take nums[i]
          if (t < k) dp_suf[idx+1][t+1][v | nums[i]] = 1;
        }
      }
    }

    int ans = 0;
    for (int i = k; i <= n - k; ++i) {
      for (int v1 = 0; v1 < W; ++v1) {
        if (!dp_pref[i][k][v1]) continue;
        for (int v2 = 0; v2 < W; ++v2) {
          if (!dp_suf[n - i][k][v2]) continue;
          ans = max(ans, v1 ^ v2);
        }
      }
    }
    return ans;
  }
};
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

package main

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

  dpPref := make([][][]bool, n+1)
  for i := 0; i <= n; i++ {
    dpPref[i] = make([][]bool, k+1)
    for t := 0; t <= k; t++ {
      dpPref[i][t] = make([]bool, W)
    }
  }
  dpPref[0][0][0] = true

  for i := 0; i < n; i++ {
    for t := 0; t <= k; t++ {
      for v := 0; v < W; v++ {
        if !dpPref[i][t][v] { continue }
        dpPref[i+1][t][v] = true
        if t < k {
          dpPref[i+1][t+1][v | nums[i]] = true
        }
      }
    }
  }

  dpSuf := make([][][]bool, n+1)
  for i := 0; i <= n; i++ {
    dpSuf[i] = make([][]bool, k+1)
    for t := 0; t <= k; t++ {
      dpSuf[i][t] = make([]bool, W)
    }
  }
  dpSuf[0][0][0] = true
  // build from right to left
  for i := n-1; i >= 0; i-- {
    idx := n-1-i
    for t := 0; t <= k; t++ {
      for v := 0; v < W; v++ {
        if !dpSuf[idx][t][v] { continue }
        dpSuf[idx+1][t][v] = true
        if t < k {
          dpSuf[idx+1][t+1][v | nums[i]] = true
        }
      }
    }
  }

  ans := 0
  for i := k; i <= n-k; i++ {
    for v1 := 0; v1 < W; v1++ {
      if !dpPref[i][k][v1] { continue }
      for v2 := 0; v2 < W; v2++ {
        if !dpSuf[n-i][k][v2] { continue }
        x := v1 ^ v2
        if x > ans { ans = x }
      }
    }
  }
  return ans
}
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.util.*;

class Solution {
  public int maxValue(int[] nums, int k) {
    int n = nums.length;
    final int W = 128;

    boolean[][][] dpPref = new boolean[n+1][k+1][W];
    dpPref[0][0][0] = true;
    for (int i = 0; i < n; ++i) {
      for (int t = 0; t <= k; ++t) {
        for (int v = 0; v < W; ++v) {
          if (!dpPref[i][t][v]) continue;
          dpPref[i+1][t][v] = true;
          if (t < k) dpPref[i+1][t+1][v | nums[i]] = true;
        }
      }
    }

    boolean[][][] dpSuf = new boolean[n+1][k+1][W];
    dpSuf[0][0][0] = true;
    for (int i = n-1; i >= 0; --i) {
      int idx = n-1-i;
      for (int t = 0; t <= k; ++t) {
        for (int v = 0; v < W; ++v) {
          if (!dpSuf[idx][t][v]) continue;
          dpSuf[idx+1][t][v] = true;
          if (t < k) dpSuf[idx+1][t+1][v | nums[i]] = true;
        }
      }
    }

    int ans = 0;
    for (int i = k; i <= n - k; ++i) {
      for (int v1 = 0; v1 < W; ++v1) {
        if (!dpPref[i][k][v1]) continue;
        for (int v2 = 0; v2 < W; ++v2) {
          if (!dpSuf[n - i][k][v2]) continue;
          ans = Math.max(ans, v1 ^ v2);
        }
      }
    }
    return ans;
  }
}
 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
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
  fun maxValue(nums: IntArray, k: Int): Int {
    val n = nums.size
    val W = 128

    val dpPref = Array(n+1) { Array(k+1) { BooleanArray(W) } }
    dpPref[0][0][0] = true
    for (i in 0 until n) {
      for (t in 0..k) {
        for (v in 0 until W) {
          if (!dpPref[i][t][v]) continue
          dpPref[i+1][t][v] = true
          if (t < k) dpPref[i+1][t+1][v or nums[i]] = true
        }
      }
    }

    val dpSuf = Array(n+1) { Array(k+1) { BooleanArray(W) } }
    dpSuf[0][0][0] = true
    for (i in n-1 downTo 0) {
      val idx = n-1-i
      for (t in 0..k) {
        for (v in 0 until W) {
          if (!dpSuf[idx][t][v]) continue
          dpSuf[idx+1][t][v] = true
          if (t < k) dpSuf[idx+1][t+1][v or nums[i]] = true
        }
      }
    }

    var ans = 0
    for (i in k..n-k) {
      for (v1 in 0 until W) {
        if (!dpPref[i][k][v1]) continue
        for (v2 in 0 until W) {
          if (!dpSuf[n - i][k][v2]) continue
          ans = maxOf(ans, v1 xor v2)
        }
      }
    }
    return ans
  }
}
 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
31
32
33
34
35
36

from typing import List

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

    dp_pref = [ [set() for _ in range(k+1)] for _ in range(n+1) ]
    dp_pref[0][0].add(0)
    for i in range(n):
      for t in range(k+1):
        for v in dp_pref[i][t]:
          dp_pref[i+1][t].add(v)
          if t < k:
            dp_pref[i+1][t+1].add(v | nums[i])

    dp_suf = [ [set() for _ in range(k+1)] for _ in range(n+1) ]
    dp_suf[0][0].add(0)
    for i in range(n-1, -1, -1):
      idx = n-1-i
      for t in range(k+1):
        for v in dp_suf[idx][t]:
          dp_suf[idx+1][t].add(v)
          if t < k:
            dp_suf[idx+1][t+1].add(v | nums[i])

    ans = 0
    for i in range(k, n - k + 1):
      left = dp_pref[i][k]
      right = dp_suf[n - i][k]
      if not left or not right:
        continue
      for v1 in left:
        for v2 in right:
          ans = max(ans, v1 ^ v2)
    return ans
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

impl Solution {
  pub fn max_value(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    let w = 128usize;

    let mut dp_pref: Vec<Vec<Vec<u8>>> = vec![vec![vec![0u8; w]; k+1]; n+1];
    dp_pref[0][0][0] = 1;
    for i in 0..n {
      for t in 0..=k {
        for v in 0..w {
          if dp_pref[i][t][v] == 0 { continue; }
          dp_pref[i+1][t][v] = 1;
          if t < k {
            let nv = v | (nums[i] as usize);
            dp_pref[i+1][t+1][nv] = 1;
          }
        }
      }
    }

    let mut dp_suf: Vec<Vec<Vec<u8>>> = vec![vec![vec![0u8; w]; k+1]; n+1];
    dp_suf[0][0][0] = 1;
    for i in (0..n).rev() {
      let idx = n-1-i;
      for t in 0..=k {
        for v in 0..w {
          if dp_suf[idx][t][v] == 0 { continue; }
          dp_suf[idx+1][t][v] = 1;
          if t < k {
            let nv = v | (nums[i] as usize);
            dp_suf[idx+1][t+1][nv] = 1;
          }
        }
      }
    }

    let mut ans = 0i32;
    for i in k..=n - k {
      for v1 in 0..w {
        if dp_pref[i][k][v1] == 0 { continue; }
        for v2 in 0..w {
          if dp_suf[n - i][k][v2] == 0 { continue; }
          ans = ans.max((v1 ^ v2) as i32);
        }
      }
    }
    ans
  }
}
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

function maxValue(nums: number[], k: number): number {
  const n = nums.length;
  const W = 128;

  const dpPref: boolean[][][] = new Array(n+1);
  for (let i = 0; i <= n; ++i) {
    dpPref[i] = new Array(k+1);
    for (let t = 0; t <= k; ++t) dpPref[i][t] = new Array(W).fill(false);
  }
  dpPref[0][0][0] = true;
  for (let i = 0; i < n; ++i) {
    for (let t = 0; t <= k; ++t) {
      for (let v = 0; v < W; ++v) {
        if (!dpPref[i][t][v]) continue;
        dpPref[i+1][t][v] = true;
        if (t < k) dpPref[i+1][t+1][v | nums[i]] = true;
      }
    }
  }

  const dpSuf: boolean[][][] = new Array(n+1);
  for (let i = 0; i <= n; ++i) {
    dpSuf[i] = new Array(k+1);
    for (let t = 0; t <= k; ++t) dpSuf[i][t] = new Array(W).fill(false);
  }
  dpSuf[0][0][0] = true;
  for (let i = n - 1; i >= 0; --i) {
    const idx = n - 1 - i;
    for (let t = 0; t <= k; ++t) {
      for (let v = 0; v < W; ++v) {
        if (!dpSuf[idx][t][v]) continue;
        dpSuf[idx+1][t][v] = true;
        if (t < k) dpSuf[idx+1][t+1][v | nums[i]] = true;
      }
    }
  }

  let ans = 0;
  for (let i = k; i <= n - k; ++i) {
    for (let v1 = 0; v1 < W; ++v1) {
      if (!dpPref[i][k][v1]) continue;
      for (let v2 = 0; v2 < W; ++v2) {
        if (!dpSuf[n - i][k][v2]) continue;
        ans = Math.max(ans, v1 ^ v2);
      }
    }
  }
  return ans;
}

Complexity

  • ⏰ Time complexity: O(n * k * W + n * W^2) – Iteratively building prefix and suffix DP tables costs O(n * k * W) and combining OR-values across splits costs O(n * W^2).
  • 🧺 Space complexity: O(n * k * W) – We store boolean DP tables for prefixes and suffixes in this straightforward bottom-up implementation.