Skip to content

3287. Find the Maximum Sequence Value of Array 👍

  • Time: $O(nk \ cdot 2^7 + n \cdot 2^7 \cdot 2^7)$
  • Space: $O(nk \cdot 2^7)$
 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
class Solution {
 public:
  int maxValue(vector<int>& nums, int k) {
    // left[i][j][x] := true if it's possible to get an OR value of x by
    // selecting j numbers from nums[0..i]
    const vector<vector<vector<bool>>> left = getPossibleORs(nums, k);
    // right[i][j][x] := true if it's possible to get an OR value of x by
    // selecting j numbers from nums[i..n - 1]
    vector<vector<vector<bool>>> right =
        getPossibleORs({nums.rbegin(), nums.rend()}, k);
    ranges::reverse(right);

    int ans = 0;

    for (int i = k - 1; i + k < nums.size(); ++i)
      for (int a = 0; a <= kMaxXor; ++a)
        for (int b = 0; b <= kMaxXor; ++b)
          if (left[i][k][a] && right[i + 1][k][b])
            ans = max(ans, a ^ b);

    return ans;
  }

 private:
  static constexpr int kMaxXor = 128;

  // Gets all possible OR values till each index and number of numbers.
  vector<vector<vector<bool>>> getPossibleORs(const vector<int>& nums, int k) {
    // dp[i][j][x] := true if it's possible to get an OR value of x by selecting
    // j numbers from nums[0..i]
    vector<vector<vector<bool>>> dp(
        nums.size(), vector<vector<bool>>(k + 1, vector<bool>(kMaxXor + 1)));

    dp[0][1][nums[0]] = true;

    // No number is selected.
    for (int i = 0; i < nums.size(); ++i)
      dp[i][0][0] = true;

    for (int i = 1; i < nums.size(); ++i)
      for (int j = 1; j <= k; ++j)
        for (int x = 0; x <= kMaxXor; ++x) {
          // 1. Skip the current number.
          if (dp[i - 1][j][x])
            dp[i][j][x] = true;
          // 2. Pick the current number.
          if (dp[i - 1][j - 1][x])
            dp[i][j][nums[i] | x] = 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
  public int maxValue(int[] nums, int k) {
    boolean[][][] left = getPossibleORs(nums, k);
    int[] reversedNums = reverseArray(nums);
    boolean[][][] right = getPossibleORs(reversedNums, k);
    reverseArray(right);

    int ans = 0;

    for (int i = k - 1; i + k < nums.length; ++i)
      for (int a = 0; a <= MAX_XOR; ++a)
        for (int b = 0; b <= MAX_XOR; ++b)
          if (left[i][k][a] && right[i + 1][k][b])
            ans = Math.max(ans, a ^ b);

    return ans;
  }

  private static final int MAX_XOR = 128;

  // Gets all possible OR values till each index and number of numbers.
  private boolean[][][] getPossibleORs(int[] nums, int k) {
    // dp[i][j][x] := true if it's possible to get an OR value of x by selecting
    // j numbers from nums[0..i]
    boolean[][][] dp = new boolean[nums.length][k + 1][MAX_XOR + 1];
    dp[0][1][nums[0]] = true;

    // No number is selected.
    for (int i = 0; i < nums.length; ++i)
      dp[i][0][0] = true;

    for (int i = 1; i < nums.length; ++i)
      for (int j = 1; j <= k; ++j)
        for (int x = 0; x <= MAX_XOR; ++x) {
          if (dp[i - 1][j][x]) // 1. Skip the current number.
            dp[i][j][x] = true;
          if (dp[i - 1][j - 1][x]) // 2. Pick the current number.
            dp[i][j][nums[i] | x] = true;
        }

    return dp;
  }

  private int[] reverseArray(int[] arr) {
    int[] reversed = new int[arr.length];
    for (int i = 0; i < arr.length; ++i)
      reversed[i] = arr[arr.length - 1 - i];
    return reversed;
  }

  private void reverseArray(boolean[][][] arr) {
    for (int l = 0, r = arr.length - 1; l < r; ++l, --r) {
      boolean[][] temp = arr[l];
      arr[l] = arr[r];
      arr[r] = temp;
    }
  }
}

 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
class Solution:
  def maxValue(self, nums: list[int], k: int) -> int:
    left = self._getPossibleORs(nums, k)
    right = self._getPossibleORs(nums[::-1], k)[::-1]
    return max(a ^ b
               for i in range(k - 1, len(nums) - k)
               for a in range(128 + 1)
               for b in range(128 + 1)
               if left[i][k][a] and right[i + 1][k][b])

  def _getPossibleORs(self, nums: list[int], k: int) -> list[list[list[bool]]]:
    dp = [[[False] * (128 + 1)
          for _ in range(k + 1)]
          for _ in range(len(nums))]

    dp[0][1][nums[0]] = True

    for i in range(len(nums)):
      dp[i][0][0] = True

    for i in range(1, len(nums)):
      for j in range(1, k + 1):
        for x in range(128 + 1):
          if dp[i - 1][j][x]:
            dp[i][j][x] = True
          if dp[i - 1][j - 1][x]:
            dp[i][j][nums[i] | x] = True

    return dp