# Find the Maximum Sequence Value of Array **Difficulty:** HARD [External](https://leetcode.com/problems/find-the-maximum-sequence-value-of-array) Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-sequence-value-of-array **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) **Data structures:** Array --- ## 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`. **Example 1:** **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:** **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` # Approaches ## Brute-Force Dynamic Programming This approach uses dynamic programming to find all possible pairs of OR-sums for two disjoint subsequences of sizes `k`. The state of our DP table will keep track of the number of elements used for each of the two subsequences and the elements from `nums` considered so far. **Time:** O(n * k^2 * C^2), where n is the length of `nums`, k is the subsequence size, and C is the maximum possible OR-sum (128). For each of the `n` numbers, we iterate through `k*k` states, and for each state, we update based on up to `C*C` existing pairs. · **Space:** O(k^2 * C^2), where C is the maximum possible OR-sum (128). This is because the DP table stores `k*k` states, and each state can hold up to `C*C` pairs. **Pros:** Conceptually straightforward application of dynamic programming.; Guaranteed to find the correct answer if it could run within time and memory limits. **Cons:** Extremely high time complexity, making it infeasible for the given constraints.; Very high space complexity, likely to cause Memory Limit Exceeded errors. ### Explanation The state can be defined as `dp[i][j1][j2]`, which stores a set of all achievable `(orA, orB)` pairs. Here, `i` is the number of elements considered from `nums`, `j1` is the size of the first subsequence (let's call it A), and `j2` is the size of the second subsequence (B). `orA` and `orB` are their respective bitwise OR-sums. The DP transition involves iterating through each number in `nums` and for each state `(j1, j2)`, deciding whether to place the current number in set A, set B, or neither. This builds up the sets of achievable OR-sum pairs. After processing all `n` numbers, the state `dp[n][k][k]` will contain all possible pairs `(orA, orB)` from two disjoint k-element subsequences. We can then iterate through this final set to find the maximum `orA XOR orB` value. Due to the enormous state space, this approach is not practical. The number of possible OR-sums is small (0-127), but the number of pairs can be up to `128*128`. A DP table of size `n * k * k * 128 * 128` is too large. Here is a conceptual representation of the logic: ```java // Conceptual code for the brute-force DP approach // Note: This is not a practical implementation due to high complexity. // dp[j1][j2] would be a Set of pairs (orA, orB) // For simplicity, let's imagine a Pair class or use an array int[2]. Set>[][] dp = new HashSet[k + 1][k + 1]; // Initialization for (int j1 = 0; j1 <= k; j1++) { for (int j2 = 0; j2 <= k; j2++) { dp[j1][j2] = new HashSet<>(); } } dp[0][0].add(new Pair<>(0, 0)); for (int num : nums) { Set>[][] newDp = new HashSet[k + 1][k + 1]; // Initialize newDp as a copy of dp for (int j1 = 0; j1 <= k; j1++) { for (int j2 = 0; j2 <= k; j2++) { for (Pair p : dp[j1][j2]) { // Option 1: Add num to set A if (j1 < k) { newDp[j1 + 1][j2].add(new Pair<>(p.getKey() | num, p.getValue())); } // Option 2: Add num to set B if (j2 < k) { newDp[j1][j2 + 1].add(new Pair<>(p.getKey(), p.getValue() | num)); } } } } dp = newDp; // This is inefficient, in-place updates are better but complex } int maxVal = 0; for (Pair p : dp[k][k]) { maxVal = Math.max(maxVal, p.getKey() ^ p.getValue()); } // return maxVal; ``` ### Algorithm - Let `dp[i][j1][j2]` be the set of all possible pairs `(orA, orB)` where `orA` is the OR-sum of a `j1`-element subsequence and `orB` is the OR-sum of a `j2`-element subsequence, both chosen from the first `i` numbers of `nums`, such that the two subsequences are disjoint. - **Base Case:** `dp[0][0][0] = {(0, 0)}`. All other sets are empty. - **Transition:** To compute `dp[i][j1][j2]`, we consider the `i`-th number, `num = nums[i-1]`. We have three choices for `num`: 1. **Don't include `num`:** The pairs in `dp[i-1][j1][j2]` are carried over to `dp[i][j1][j2]`. 2. **Include `num` in the first set (A):** For every pair `(orA_prev, orB)` in `dp[i-1][j1-1][j2]`, we can form a new pair `(orA_prev | num, orB)` for `dp[i][j1][j2]`. 3. **Include `num` in the second set (B):** For every pair `(orA, orB_prev)` in `dp[i-1][j1][j2-1]`, we can form a new pair `(orA, orB_prev | num)` for `dp[i][j1][j2]`. - **Final Result:** After filling the table up to `i=n`, the set `dp[n][k][k]` contains all possible `(orA, orB)` pairs. The maximum sequence value is the maximum of `orA XOR orB` over all pairs in this set. - **Space Optimization:** Notice that `dp[i]` only depends on `dp[i-1]`. We can optimize space by using only two layers of the DP table (for the `i` dimension) or by updating in place with careful loop ordering. ## Greedy Bitwise Search with Dynamic Programming A much more efficient approach involves a greedy strategy combined with dynamic programming. We can construct the maximum value bit by bit, from most significant to least significant. For each bit position, we greedily check if we can make that bit a '1' in our final answer, given the choices we've made for the higher-order bits. **Time:** O(B * n * k * C), where B is the number of bits (constant, 7), n is the length of `nums`, k is the subsequence size, and C is the maximum possible OR-sum (128). This simplifies to O(n * k) as B and C are small constants. · **Space:** O(k * C), where C is the maximum possible OR-sum (128). The DP table inside the `isPossible` function is of size `(k+1) x 128`. **Pros:** Significantly more efficient than the brute-force DP approach.; The time and space complexity are well within the limits for the given constraints.; The greedy bit-by-bit strategy is a powerful technique for maximization problems involving bitwise operations. **Cons:** The logic, especially the DP state within the greedy check, can be complex to formulate and implement correctly. ### Explanation We iterate from bit 6 down to 0. Let's say our current best-achievable value is `ans`. For the current bit `b`, we test if we can achieve a value of `ans | (1 << b)`. This test involves checking if there exist two disjoint `k`-element subsequences, A and B, such that `(OR(A) XOR OR(B))` matches `ans | (1 << b)` on all bits from 6 down to `b`. To perform this check, we use a DP helper function, `isPossible(target)`. This function determines if a given `target` prefix is achievable. The state for this DP is `dp[j1][pA]`, which stores the minimum number of elements (`j2`) needed for set B to satisfy the prefix condition, given that set A has `j1` elements and its OR-sum, when masked with the current bitmask, results in `pA`. The DP table `dp` has dimensions `(k+1) x 128`. `dp[j1][pA]` is initialized to a value larger than `k` (e.g., `k+1`), with `dp[0][0] = 0`. We iterate through each `num` in `nums`. For each `num`, we create a new DP table `new_dp` based on the old `dp` table to represent the states after considering `num`. For each state `(j1, pA)` with `j2 = dp[j1][pA]`, we have three choices for `num`: 1. **Don't use `num`:** The state is carried over, which is implicitly handled by copying `dp` to `new_dp`. 2. **Add `num` to set A:** If `j1 < k`, we can transition to a state with `j1+1` elements in A. The new OR-sum prefix for A will be `pA | (num & mask)`. We update `new_dp[j1+1][pA | (num & mask)]` with `min(current_value, j2)`. 3. **Add `num` to set B:** If `j2 < k`, we can transition to a state with `j2+1` elements in B. The OR-sum prefix for B changes, which in turn changes the required prefix for A to maintain the `target` XOR relationship. The new required `pA` is calculated, and we update `new_dp` accordingly. After processing all numbers, if there is any `pA` for which `dp[k][pA] <= k`, it means we can form two valid sets of size `k`, and the function returns `true`. ```java class Solution { public int maxSequenceValue(int[] nums, int k) { int ans = 0; for (int b = 6; b >= 0; b--) { int target = ans | (1 << b); if (isPossible(nums, k, target, b)) { ans = target; } } return ans; } private boolean isPossible(int[] nums, int k, int target, int bit) { int mask = 0; for (int i = 6; i >= bit; i--) { mask |= (1 << i); } int[][] dp = new int[k + 1][128]; for (int i = 0; i <= k; i++) { for (int j = 0; j < 128; j++) { dp[i][j] = k + 1; // Use k+1 as infinity } } dp[0][0] = 0; for (int num : nums) { int numPrefix = num & mask; int[][] newDp = new int[k + 1][128]; for(int i=0; i<=k; i++) { System.arraycopy(dp[i], 0, newDp[i], 0, 128); } for (int j1 = 0; j1 <= k; j1++) { for (int pA = 0; pA < 128; pA++) { if (dp[j1][pA] > k) continue; int j2 = dp[j1][pA]; // Option 1: Add num to set A if (j1 < k) { newDp[j1 + 1][pA | numPrefix] = Math.min(newDp[j1 + 1][pA | numPrefix], j2); } // Option 2: Add num to set B if (j2 < k) { int pB = pA ^ target; int newPB = pB | numPrefix; int newPA = newPB ^ target; newDp[j1][newPA] = Math.min(newDp[j1][newPA], j2 + 1); } } } dp = newDp; } for (int pA = 0; pA < 128; pA++) { if (dp[k][pA] <= k) { return true; } } return false; } } ``` ### Algorithm - The core idea is to build the maximum possible result bit by bit, from the most significant bit (MSB) to the least significant bit (LSB). - Initialize the result `ans = 0`. - Iterate from bit `b = 6` down to 0 (since `nums[i] < 2^7`). - In each iteration, try to set the `b`-th bit of the answer to 1. Let `target = ans | (1 << b)`. - Check if it's possible to find two disjoint `k`-element subsequences A and B such that their OR-sums `orA` and `orB` satisfy `(orA XOR orB)` having `target` as a prefix. This means for all bits `j >= b`, the `j`-th bit of `(orA XOR orB)` must match the `j`-th bit of `target`. - This check is performed by a helper function, `isPossible(target, b)`. - If `isPossible` returns true, it means we can achieve this `target` prefix, so we update `ans = target`. - If it returns false, we cannot set the `b`-th bit to 1 (while satisfying higher bits), so we leave `ans` as is and proceed to the next smaller bit. - The `isPossible` function uses its own DP. Let `dp[j1][pA]` be the minimum size `j2` of the second set (B) required to satisfy the prefix condition, given that the first set (A) has `j1` elements and its OR-sum prefix is `pA`. The prefix is calculated by `val & mask`, where `mask` includes all bits from MSB down to `b`. - The DP transition for `isPossible` considers adding the current number to set A, set B, or neither, and updates the minimum `j2` values accordingly. - After iterating through all bits, `ans` holds the maximum possible sequence value. # Solutions ### Java ```java class Solution { public int maxValue(int[] nums, int k) { int m = 1 << 7; int n = nums.length; boolean[][][] f = new boolean[n + 1][k + 2][m]; f[0][0][0] = true; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { for (int x = 0; x < m; x++) { if (f[i][j][x]) { f[i + 1][j][x] = true; f[i + 1][j + 1][x | nums[i]] = true; } } } } boolean[][][] g = new boolean[n + 1][k + 2][m]; g[n][0][0] = true; for (int i = n; i > 0; i--) { for (int j = 0; j <= k; j++) { for (int y = 0; y < m; y++) { if (g[i][j][y]) { g[i - 1][j][y] = true; g[i - 1][j + 1][y | nums[i - 1]] = true; } } } } int ans = 0; for (int i = k; i <= n - k; i++) { for (int x = 0; x < m; x++) { if (f[i][k][x]) { for (int y = 0; y < m; y++) { if (g[i][k][y]) { ans = Math.max(ans, x ^ y); } } } } } return ans; } } ``` ### CPP ```cpp class Solution { public: int maxValue(vector &nums, int k) { int m = 1 << 7; int n = nums.size(); vector>> f( n + 1, vector>(k + 2, vector(m, false))); f[0][0][0] = true; for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { for (int x = 0; x < m; x++) { if (f[i][j][x]) { f[i + 1][j][x] = true; f[i + 1][j + 1][x | nums[i]] = true; } } } } vector>> g( n + 1, vector>(k + 2, vector(m, false))); g[n][0][0] = true; for (int i = n; i > 0; i--) { for (int j = 0; j <= k; j++) { for (int y = 0; y < m; y++) { if (g[i][j][y]) { g[i - 1][j][y] = true; g[i - 1][j + 1][y | nums[i - 1]] = true; } } } } int ans = 0; for (int i = k; i <= n - k; i++) { for (int x = 0; x < m; x++) { if (f[i][k][x]) { for (int y = 0; y < m; y++) { if (g[i][k][y]) { ans = max(ans, x ^ y); } } } } } return ans; } }; ``` ### Python ```python class Solution: def maxValue(self, nums: List[int], k: int) -> int: m = 1 << 7 n = len(nums) f = [[[False] * m for _ in range(k + 2)] for _ in range(n + 1)] f[0][0][0] = True for i in range(n): for j in range(k + 1): for x in range(m): f[i + 1][j][x] |= f[i][j][x] f[i + 1][j + 1][x | nums[i]] |= f[i][j][x] g = [[[False] * m for _ in range(k + 2)] for _ in range(n + 1)] g[n][0][0] = True for i in range(n, 0, - 1): for j in range(k + 1): for y in range(m): g[i - 1][j][y] |= g[i][j][y] g[i - 1][j + 1][y | nums[i - 1]] |= g[i][j][y] ans = 0 for i in range(k, n - k + 1): for x in range(m): if f[i][k][x]: for y in range(m): if g[i][k][y]: ans = max(ans, x ^ y) return ans ```