Find the Maximum Sequence Value of Array - Practice Coding Problems

Find the Maximum Sequence Value of 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,6,7], k = 1

› Output: 5

💡 Note: Choose subsequence [2,7]. First half: OR(2) = 2. Second half: OR(7) = 7. XOR: 2 ^ 7 = 5

Example 2 — Larger k

$ Input: nums = [4,2,5,6,7], k = 2

› Output: 2

💡 Note: Choose subsequence [4,5,6,7]. First half: OR(4,5) = 5. Second half: OR(6,7) = 7. XOR: 5 ^ 7 = 2

Example 3 — All Same Values

$ Input: nums = [3,3,3,3], k = 2

› Output: 0

💡 Note: Any subsequence gives OR(3,3) = 3 for both halves. XOR: 3 ^ 3 = 0

Constraints

1 ≤ k ≤ nums.length ≤ 50
1 ≤ nums[i] ≤ 2⁶
nums.length is even
2 * k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and parameter k

Choose Subsequence

Pick 2k elements and split into two groups of k

Compute Value

OR each group, then XOR the results

Key Takeaway

🎯 Key Insight: Use DP to build all possible OR values efficiently, then find maximum XOR

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is to use dynamic programming to efficiently build all possible OR combinations for subsequences of each size, then find the maximum XOR between two sets of size k. The optimal approach uses space-optimized DP with pruning. Time: O(n * k * V), Space: O(k * V).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DP with Early Pruning	O(n * k * V)	O(k * V)	Enhanced DP with pruning and memory optimization
Brute Force - Generate All Subsequences	O(C(n,2k) * k)	O(1)	Generate all possible subsequences of size 2k and calculate their sequence values
Dynamic Programming with Bitmask	O(n * k * V²)	O(n * k * V)	Use DP to track all possible OR values for each subsequence size

Optimized DP with Early Pruning — Algorithm Steps

Step 1: Use rolling array to optimize space from O(n*k*V) to O(k*V)
Step 2: Prune impossible OR values early to reduce search space
Step 3: Use bit manipulation to efficiently compute OR combinations
Step 4: Apply meet-in-the-middle technique for large k values

Visualization

Tap to expand

Step-by-Step Walkthrough

Rolling Array

Use only current and previous states

Prune Values

Remove impossible OR combinations early

Optimized XOR

Check only unique pairs to avoid duplicates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VAL 1024
#define MAX_K 25

int solution(int* nums, int numsSize, int k) {
    // Use boolean arrays for space efficiency
    static int prev[MAX_K+1][MAX_VAL];
    static int curr[MAX_K+1][MAX_VAL];
    
    memset(prev, 0, sizeof(prev));
    memset(curr, 0, sizeof(curr));
    
    // Base case
    prev[0][0] = 1;
    
    // Fill DP table with space optimization
    for (int i = 0; i < numsSize; i++) {
        memset(curr, 0, sizeof(curr));
        
        for (int j = 0; j <= k; j++) {
            // Copy from previous
            for (int val = 0; val < MAX_VAL; val++) {
                if (prev[j][val]) {
                    curr[j][val] = 1;
                }
            }
            
            if (j > 0) {
                for (int val = 0; val < MAX_VAL; val++) {
                    if (prev[j-1][val]) {
                        int newOr = val | nums[i];
                        if (newOr < MAX_VAL) {
                            curr[j][newOr] = 1;
                        }
                    }
                }
            }
        }
        
        // Swap for next iteration
        memcpy(prev, curr, sizeof(curr));
    }
    
    // Find maximum XOR
    int maxValue = 0;
    for (int or1 = 0; or1 < MAX_VAL; or1++) {
        if (prev[k][or1]) {
            for (int or2 = or1; or2 < MAX_VAL; or2++) {
                if (prev[k][or2]) {
                    int value = or1 ^ or2;
                    if (value > maxValue) {
                        maxValue = value;
                    }
                }
            }
        }
    }
    
    return maxValue;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * k * V)

n elements, k sizes, V unique OR values (pruned)

✓ Linear Growth

Space Complexity

O(k * V)

Rolling DP array with only current and previous states

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DP with Early Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler