## Intuition The problem asks us to find a subsequence of an array such that the value of the subsequence is maximized. The value is determined by the number of elements in the subsequence that have a particular bit set. Specifically, for a subsequence of size `k`, we need at least `max(1, k-2)` elements to have a particular bit set for that bit to contribute to the value. Given the constraints, a brute force approach is feasible. We can try all possible subsequences of size up to 3, as the contribution of bits is determined by the majority presence in small subsequences. ## Approach 1. **Brute Force on Small Subsequences**: Since the maximum size of the array is 500, and we are interested in subsequences of size up to 3, we can afford to check all possible combinations of 1, 2, and 3 elements. 2. **Calculate Value for Each Subsequence**: - For each subsequence, determine which bits are set in at least `max(1, k-2)` elements. - Calculate the value of the subsequence by summing `2^i` for each bit `i` that satisfies the condition. 3. **Iterate Over All Combinations**: - For each element, consider it alone. - For each pair of elements, consider them together. - For each triplet of elements, consider them together. - Keep track of the maximum value found. 4. **Output the Maximum Value**. ## Complexity - **Time Complexity**: \(O(n^3 \cdot \log(\text{max\_bit}))\), where `n` is the size of the array and `max_bit` is the number of bits needed to represent the largest number in the array. This is feasible given the constraints. - **Space Complexity**: \(O(1)\), aside from input storage. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } long long max_value = 0; // Check all single elements for (int i = 0; i < n; ++i) { max_value = max(max_value, a[i]); } // Check all pairs for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { max_value = max(max_value, a[i] | a[j]); } } // Check all triplets for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { max_value = max(max_value, a[i] | a[j] | a[k]); } } } cout << max_value << '\n'; return 0; } ``` This solution efficiently computes the maximum subsequence value by considering all possible subsequences of size 1, 2, and 3, using bitwise OR to determine the contribution of each bit.

Maximum Subsequence Value

Problem Details