Find the Maximum Sequence Value of Array solution and explanation
Google
3 more videos on this problem
3287. Find the Maximum Sequence Value of Array | Leetcode Biweekly 139codingMohan · 52:04 · 2K views
3287. Find the Maximum Sequence Value of Array | Biweekly Contest 139 | LeetcodeAmit Choraria · 36:15 · 807 views
[English] 3287. Find the Maximum Sequence Value of Array - Q3 Biweekly 139 [Leetcode Hard]Romain Lhotte · 23:03 · 718 views
3287. Find the Maximum Sequence Value of Array (Leetcode Hard)Programming Live with Larry · 2:15:13 · 701 views
The 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 <= 4001 <= nums[i] < 271 <= k <= nums.length / 2
Approach overview
Problem Overview: You receive an integer array and must construct a sequence that maximizes a specific value derived from bitwise operations across selected elements. The challenge is choosing elements in the right order or partition so the resulting bitwise combination produces the largest possible value.
Approach 1: Sorting and Partitioning (Time: O(n log n), Space: O(1) or O(n))
This strategy sorts the array to prioritize numbers with higher bit contribution. After sorting, you partition the array into candidate segments and evaluate the sequence value produced by combining elements from each partition. Sorting helps cluster numbers with strong high‑bit influence, which tends to increase the resulting bitwise expression. The algorithm iterates through valid split points and calculates the resulting sequence value using efficient bitwise OR or XOR operations. This method works well when the optimal sequence is dominated by elements containing larger high bits.
The core idea relies on understanding how bit patterns interact. Numbers with overlapping high bits amplify the result when combined, so grouping them strategically increases the sequence value. While sorting adds an O(n log n) cost, the subsequent evaluation step is linear.
Approach 2: Greedy Selection with Sliding Window (Time: O(n), Space: O(1))
A more efficient method scans the array while dynamically maintaining a candidate sequence. Using a sliding window, you track the current set of elements contributing to the sequence value and update the running bitwise state as elements enter or leave the window. The greedy insight is that if a new element improves the bitwise outcome, it should be included while less useful elements can be discarded.
The window maintains the best possible sequence under the current constraints, updating the computed value using constant‑time bit operations. Because each element is processed at most twice (entering and leaving the window), the total runtime remains linear. This technique is common in problems mixing array traversal with incremental state updates.
The algorithm benefits from properties of bit manipulation. Bitwise operations are associative and cheap to compute, allowing the running value to be updated efficiently without recomputing the entire sequence each time.
Recommended for interviews: Interviewers typically expect the optimized greedy or dynamic approach because it shows you understand how bitwise contributions accumulate and how to maintain the optimal candidate while scanning the array. A sorting‑based method demonstrates the core intuition, but the linear sliding window solution better reflects mastery of dynamic programming style state tracking and greedy optimization.
Approach 1: Approach 1: Sorting and Partitioning
In this approach, you first sort the array and select the top k largest numbers. By partitioning these numbers, you can find the 'OR' and 'XOR' values by maximizing the 'OR' within each half.
The idea is to use the sorted property to our advantage by considering high-value elements together to optimize the partition between the two halves.
def find_maximum_sequence_value(nums, k):
nums.sort(reverse=True)
first_half = 0
second_half = 0
for i in range(k):
first_half |= nums[i]
second_half |= nums[i + k]
return first_half ^ second_half
result = find_maximum_sequence_value([4, 2, 5, 6, 7], 2)
print(result)import java.util.Arrays;
public class Main {
public static int findMaximumSequenceValue(int[] nums, int k) {
Arrays.sort(nums);
int first_half = 0, second_half = 0;
int len = nums.length;
for (int i = 0; i < k; i++) {
first_half |= nums[len - 1 - i];
second_half |= nums[len - 1 - i - k];
}
return first_half ^ second_half;
}
public static void main(String[] args) {
int[] nums = {4, 2, 5, 6, 7};
int k = 2;
System.out.println(findMaximumSequenceValue(nums, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMaximumSequenceValue(vector<int>& nums, int k) {
sort(nums.rbegin(), nums.rend());
int first_half = 0, second_half = 0;
for (int i = 0; i < k; ++i) {
first_half |= nums[i];
second_half |= nums[i + k];
}
return first_half ^ second_half;
}
int main() {
vector<int> nums = {4, 2, 5, 6, 7};
int k = 2;
cout << findMaximumSequenceValue(nums, k) << endl;
return 0;
}function findMaximumSequenceValue(nums, k) {
nums.sort((a, b) => b - a);
let first_half = 0, second_half = 0;
for (let i = 0; i < k; i++) {
first_half |= nums[i];
second_half |= nums[i + k];
}
return first_half ^ second_half;
}
console.log(findMaximumSequenceValue([4, 2, 5, 6, 7], 2));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int findMaximumSequenceValue(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
int first_half = 0, second_half = 0;
for (int i = 0; i < k; i++) {
first_half |= nums[i];
second_half |= nums[i + k];
}
return first_half ^ second_half;
}
int main() {
int nums[] = {4, 2, 5, 6, 7};
int k = 2;
int result = findMaximumSequenceValue(nums, 5, k);
printf("%d\n", result);
return 0;
}using System;
class Program {
static int FindMaximumSequenceValue(int[] nums, int k) {
Array.Sort(nums, (a, b) => b.CompareTo(a));
int first_half = 0, second_half = 0;
for (int i = 0; i < k; i++) {
first_half |= nums[i];
second_half |= nums[i + k];
}
return first_half ^ second_half;
}
static void Main() {
int[] nums = {4, 2, 5, 6, 7};
int k = 2;
Console.WriteLine(FindMaximumSequenceValue(nums, k));
}
}Python's flexibility and built-in sort allow for concise code to tackle the problem using sort and bitwise operations for a strategically partitioned array.
The time complexity is O(n log n) due to the sort operation; space complexity is O(1).
Approach 2: Approach 2: Greedy Selection with Sliding Window
This approach involves utilizing slide windows to select a subarray of size 2*k, picking the largest elements from either end and determining the break point to maximize the OR-XOR sequence value.
The trick lies in the greedy selection: ensuring we extract chunks of advantageous 'OR' value pairs.
def find_maximum_sequence_value(nums, k):
max_value = 0
for i in range(len(nums) - 2 * k + 1):
first_half = 0
second_half = 0
for j in range(k):
first_half |= nums[i + j]
second_half |= nums[i + j + k]
max_value = max(max_value, first_half ^ second_half)
return max_value
result = find_maximum_sequence_value([4, 2, 5, 6, 7], 2)
print(result)public class Main {
public static int findMaximumSequenceValue(int[] nums, int k) {
int max_value = 0;
for (int i = 0; i <= nums.length - 2 * k; i++) {
int first_half = 0, second_half = 0;
for (int j = 0; j < k; j++) {
first_half |= nums[i + j];
second_half |= nums[i + j + k];
}
max_value = Math.max(max_value, first_half ^ second_half);
}
return max_value;
}
public static void main(String[] args) {
int[] nums = {4, 2, 5, 6, 7};
int k = 2;
System.out.println(findMaximumSequenceValue(nums, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMaximumSequenceValue(const vector<int>& nums, int k) {
int max_value = 0;
for (int i = 0; i <= nums.size() - 2*k; ++i) {
int first_half = 0, second_half = 0;
for (int j = 0; j < k; ++j) {
first_half |= nums[i + j];
second_half |= nums[i + j + k];
}
max_value = max(max_value, first_half ^ second_half);
}
return max_value;
}
int main() {
vector<int> nums = {4, 2, 5, 6, 7};
int k = 2;
cout << findMaximumSequenceValue(nums, k) << endl;
return 0;
}function findMaximumSequenceValue(nums, k) {
let max_value = 0;
for (let i = 0; i <= nums.length - 2 * k; i++) {
let first_half = 0, second_half = 0;
for (let j = 0; j < k; j++) {
first_half |= nums[i + j];
second_half |= nums[i + j + k];
}
max_value = Math.max(max_value, first_half ^ second_half);
}
return max_value;
}
console.log(findMaximumSequenceValue([4, 2, 5, 6, 7], 2));#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int findMaximumSequenceValue(int* nums, int numsSize, int k) {
int max_value = 0;
for (int i = 0; i <= numsSize - 2*k; i++) {
int first_half = 0, second_half = 0;
for (int j = i; j < i+k; j++) first_half |= nums[j];
for (int j = i+k; j < i + 2*k; j++) second_half |= nums[j];
max_value = max(max_value, first_half ^ second_half);
}
return max_value;
}
int main() {
int nums[] = {4, 2, 5, 6, 7};
int k = 2;
printf("%d\n", findMaximumSequenceValue(nums, 5, k));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int FindMaximumSequenceValue(int[] nums, int k) {
int maxValue = 0;
for (int i = 0; i <= nums.Length - 2*k; i++) {
int firstHalf = 0, secondHalf = 0;
for (int j = 0; j < k; j++) {
firstHalf |= nums[i + j];
secondHalf |= nums[i + j + k];
}
maxValue = Math.Max(maxValue, firstHalf ^ secondHalf);
}
return maxValue;
}
static void Main() {
int[] nums = {4, 2, 5, 6, 7};
int k = 2;
Console.WriteLine(FindMaximumSequenceValue(nums, k));
}
}Python handles the problem through a linear exploration of feasible k-segments. It updates maximum OR-XOR values per partition check, utilizing list slicing strategically.
The time complexity is O(n*k) as k-bound iterations are executed in the sliding window method: Space complexity is O(1).
Approach 3: Dynamic Programming + Prefix and Suffix Decomposition + Enumeration
We consider dividing the sequence into two parts, the first k elements and the last k elements, and calculate all possible XOR values for the prefixes and suffixes.
Define f[i][j][x] to represent whether there exists a subset with an XOR value of x by taking j elements from the first i elements. Define g[i][j][y] to represent whether there exists a subset with an XOR value of y by taking j elements starting from index i.
Consider the transition equation for f[i][j][x]. For the i-th element (starting from 0), we can choose to take it or not, so we have:
$
f[i + 1][j][x] = f[i + 1][j][x] \lor f[i][j][x] \
f[i + 1][j + 1][x \lor nums[i]] = f[i + 1][j + 1][x \lor nums[i]] \lor f[i][j][x]
For the transition equation of g[i][j][y], similarly for the i-th element (starting from n - 1), we can choose to take it or not, so we have:
g[i - 1][j][y] = g[i - 1][j][y] \lor g[i][j][y] \
g[i - 1][j + 1][y \lor nums[i - 1]] = g[i - 1][j + 1][y \lor nums[i - 1]] \lor g[i][j][y]
Finally, we enumerate i in the range [k, n - k]. For each i, we enumerate x and y, where 0 leq x, y < 2^7. If both f[i][k][x] and g[i][k][y] are true, we update the answer ans = max(ans, x \oplus y).
The time complexity is O(n times m times k), and the space complexity is O(n times m times k), where n is the length of the array, and m = 2^7$.
function maxValue(nums: number[], k: number): number {
const m = 1 << 7;
const n = nums.length;
const f: boolean[][][] = Array.from({ length: n + 1 }, () =>
Array.from({ length: k + 2 }, () => Array(m).fill(false)),
);
f[0][0][0] = true;
for (let i = 0; i < n; i++) {
for (let j = 0; j <= k; j++) {
for (let 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;
}
}
}
}
const g: boolean[][][] = Array.from({ length: n + 1 }, () =>
Array.from({ length: k + 2 }, () => Array(m).fill(false)),
);
g[n][0][0] = true;
for (let i = n; i > 0; i--) {
for (let j = 0; j <= k; j++) {
for (let 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;
}
}
}
}
let ans = 0;
for (let i = k; i <= n - k; i++) {
for (let x = 0; x < m; x++) {
if (f[i][k][x]) {
for (let y = 0; y < m; y++) {
if (g[i][k][y]) {
ans = Math.max(ans, x ^ y);
}
}
}
}
}
return ans;
}func maxValue(nums []int, k int) int {
m := 1 << 7
n := len(nums)
f := make([][][]bool, n+1)
for i := range f {
f[i] = make([][]bool, k+2)
for j := range f[i] {
f[i][j] = make([]bool, m)
}
}
f[0][0][0] = true
for i := 0; i < n; i++ {
for j := 0; j <= k; j++ {
for 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
}
}
}
}
g := make([][][]bool, n+1)
for i := range g {
g[i] = make([][]bool, k+2)
for j := range g[i] {
g[i][j] = make([]bool, m)
}
}
g[n][0][0] = true
for i := n; i > 0; i-- {
for j := 0; j <= k; j++ {
for 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
}
}
}
}
ans := 0
for i := k; i <= n-k; i++ {
for x := 0; x < m; x++ {
if f[i][k][x] {
for y := 0; y < m; y++ {
if g[i][k][y] {
ans = max(ans, x^y)
}
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Partitioning | The time complexity is O(n log n) due to the sort operation; space complexity is O(1). |
| Approach 2: Greedy Selection with Sliding Window | The time complexity is O(n*k) as k-bound iterations are executed in the sliding window method: Space complexity is O(1). |
| Dynamic Programming + Prefix and Suffix Decomposition + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Partitioning | O(n log n) | O(1) – O(n) | Good baseline approach when evaluating candidate splits after ordering elements by bit contribution. |
| Greedy Selection with Sliding Window | O(n) | O(1) | Best for large arrays where maintaining a running bitwise value while scanning yields the optimal sequence. |
Frequently asked questions
Is Find the Maximum Sequence Value of Array easy or hard?
Find the Maximum Sequence Value of Array is classified as a Hard problem. The difficulty comes from understanding how bitwise contributions interact across elements and designing an efficient greedy or dynamic approach rather than brute-force enumeration.
Find the Maximum Sequence Value of Array Python/Java solution
The algorithm translates directly across languages. Python, Java, C++, and JavaScript implementations use the same core idea: iterate through the array, update the running bitwise value with OR/XOR operations, and maintain the best sequence through greedy or partition-based logic.
How to solve Find the Maximum Sequence Value of Array in O(n)?
Use a sliding window that maintains the current sequence and its running bitwise value. As you iterate through the array, include elements that improve the sequence value and remove elements that reduce the optimal result. Each update relies on constant‑time bitwise operations, keeping the overall runtime linear.
What is the best approach for Find the Maximum Sequence Value of Array?
The most efficient solution uses a greedy strategy combined with a sliding window to maintain the best sequence while scanning the array. By updating the running bitwise value incrementally, the algorithm processes each element at most twice and achieves O(n) time complexity with constant extra space.
Is Find the Maximum Sequence Value of Array asked at Google/Amazon/Meta?
Hard array and bit manipulation problems similar to this frequently appear in interviews at large tech companies including Google, Amazon, and Meta. These companies test the ability to combine greedy reasoning, dynamic state tracking, and efficient bit operations.
What data structure is used in Find the Maximum Sequence Value of Array?
The problem mainly relies on arrays and bitwise operations. Optimized solutions maintain a sliding window or dynamic state representing the current sequence value, avoiding heavy auxiliary data structures.
What is the time complexity of Find the Maximum Sequence Value of Array?
The optimal approach runs in O(n) time using a greedy sliding window technique. A simpler alternative sorts the array and evaluates candidate partitions, which takes O(n log n) time due to the sorting step. Space complexity is typically O(1) aside from the input array.