We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Sequence Value of Array

Number: 3575

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an integer array nums and a positive integer k, pick a subsequence of nums with exactly 2 * k elements (keeping the original order). Split the subsequence into two halves: the first k elements and the last k elements. Compute the value of the subsequence as   (OR of all elements in first half) XOR (OR of all elements in second half). Return the maximum possible value over all such subsequences.

Key Insights

  • The subsequence is not necessarily contiguous, but the order is preserved. The first k chosen form one group and the next k form the second.
  • Since numbers are small (< 2^7) the OR sums are bounded (0 to 127), meaning state dimensions related to OR values are small.
  • We can separate the problem into two parts: selecting k elements for the left half and k elements for the right half, while ensuring the left group comes entirely before the right.
  • Use dynamic programming from the left to build all possible OR values for picking k elements from the prefix and another DP from the right for picking k elements from a suffix.
  • Combine the DP results in a “split” fashion over all indices to maximize (left OR) XOR (right OR).

Space and Time Complexity

Time Complexity: O(n^2 * (max_OR)^2) ~ O(400^2 * 128^2) in worst-case (using DP over positions, count and OR states)
Space Complexity: O(n * k * max_OR) for each DP table, which is manageable given the constraints.

Solution

The solution employs a two-pass DP technique. First, construct a DP table (leftDP) over the prefix of nums that calculates all OR values possible for every count c (0 ≤ c ≤ k) when picking c elements. Here, leftDP[i][c] is a set of possible OR values obtained by considering nums[0..i]. Similarly, construct rightDP for the suffix of nums so that rightDP[i][c] is the set of OR values possible when picking c elements from nums[i..n-1]. Then, for every possible splitting index i (where the left group is chosen from the prefix ending at i and the right group is chosen from the suffix starting at i+1), iterate over all possible OR values in leftDP and rightDP and compute the XOR. The answer is the maximum XOR value computed.

Important details include:

  • The ordering constraint is automatically handled by splitting the problem at index i.
  • The DP transitions update the OR as new elements are included.
  • Although a 4D DP (index, count, OR value) is possible, splitting into left and right DPs reduces complexity since the OR values range is small.
  • This approach avoids iterating over all subsequences directly by exploiting bit-level bounds of the numbers.

Code Solutions

# Python Solution

# Define the function to calculate maximum sequence value.
def maxSequenceValue(nums, k):
    n = len(nums)
    max_or = 128  # since nums[i] < 2^7, OR values range from 0 to 127.

    # Build leftDP: for i in range(n), dp_left[i][c] will hold a set of possible OR values 
    # by choosing exactly c elements from the prefix nums[0..i].
    dp_left = [ [set() for _ in range(k+1)] for _ in range(n) ]
    # Base: at index 0, we can choose 0 elements or 1 if we take nums[0].
    dp_left[0][0].add(0)
    dp_left[0][1].add(nums[0])
    for i in range(1, n):
        for cnt in range(k+1):
            # Not picking the i-th element: copy previous states.
            dp_left[i][cnt] |= dp_left[i-1][cnt]
            # Picking the i-th element if we still can.
            if cnt > 0:
                for prev in dp_left[i-1][cnt-1]:
                    dp_left[i][cnt].add(prev | nums[i])
    
    # Build rightDP from the right side. 
    # dp_right[i][c] will hold possible OR values by choosing exactly c elements from nums[i..n-1].
    dp_right = [ [set() for _ in range(k+1)] for _ in range(n) ]
    dp_right[n-1][0].add(0)
    dp_right[n-1][1].add(nums[n-1])
    for i in range(n-2, -1, -1):
        for cnt in range(k+1):
            # Not picking the i-th element
            dp_right[i][cnt] |= dp_right[i+1][cnt]
            # Picking the i-th element if possible
            if cnt > 0:
                for prev in dp_right[i+1][cnt-1]:
                    dp_right[i][cnt].add(prev | nums[i])
    
    # Now iterate over possible split positions.
    # left group is chosen in prefix up to some index i and right group is chosen from i+1 to n-1.
    max_value = 0
    for i in range(n-1):
        if dp_left[i][k] and dp_right[i+1][k]:
            # For each combination of OR values in left and right halves.
            for left_val in dp_left[i][k]:
                for right_val in dp_right[i+1][k]:
                    max_value = max(max_value, left_val ^ right_val)
    return max_value

# Example usage:
print(maxSequenceValue([2,6,7], 1))     # Expected output: 5
print(maxSequenceValue([4,2,5,6,7], 2))   # Expected output: 2
← Back to All Questions