3287. Find the Maximum Sequence Value of Array LeetCode Solution
In this guide, you will get 3287. Find the Maximum Sequence Value of Array LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Sequence Value of Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Time Complexity: O(nk \ cdot 2^7 + n \cdot 2^7 \cdot 2^7)
Space Complexity: O(nk \cdot 2^7)
3287. Find the Maximum Sequence Value of Array LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3287. Find the Maximum Sequence Value of Array LeetCode Solution in Java
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 <= kMaxXor; ++a)
for (int b = 0; b <= kMaxXor; ++b)
if (left[i][k][a] && right[i + 1][k][b])
ans = Math.max(ans, a ^ b);
return ans;
}
private static final int kMaxXor = 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][kMaxXor + 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 <= kMaxXor; ++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;
}
}
} // code provided by PROGIEZ
3287. Find the Maximum Sequence Value of Array LeetCode Solution in Python
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 # code by PROGIEZ
