1class Solution {
2    /**
3     * Finds the length of the longest subsequence where every adjacent pair
4     * of elements shares at least one common set bit (i.e., their bitwise AND
5     * is non-zero). Since a subsequence chained by a common bit must have all
6     * "linked" elements sharing the SAME bit position when treated greedily,
7     * we examine each bit position independently and find the Longest
8     * Increasing Subsequence (LIS) among numbers that have that bit set.
9     *
10     * @param nums the input array
11     * @return the maximum length found across all bit positions
12     */
13    public int longestSubsequence(int[] nums) {
14        int ans = 0;
15
16        // Determine the maximum value to know how many bits we need to inspect.
17        int max = 0;
18        for (int x : nums) {
19            max = Math.max(max, x);
20        }
21
22        // Number of significant bits in the maximum value.
23        int bitCount = 32 - Integer.numberOfLeadingZeros(max);
24
25        // For each bit position, collect numbers having that bit set,
26        // then compute the LIS over that filtered list.
27        for (int bit = 0; bit < bitCount; bit++) {
28            List<Integer> filtered = new ArrayList<>();
29            for (int x : nums) {
30                // Keep the value only if its current bit is 1.
31                if (((x >> bit) & 1) == 1) {
32                    filtered.add(x);
33                }
34            }
35            ans = Math.max(ans, lis(filtered));
36        }
37
38        return ans;
39    }
40
41    /**
42     * Computes the length of the Longest Increasing Subsequence (strictly
43     * increasing) using the patience-sorting / binary-search technique.
44     *
45     * @param arr the list of values, in their original relative order
46     * @return the length of the longest strictly increasing subsequence
47     */
48    private int lis(List<Integer> arr) {
49        // 'tails' holds the smallest possible tail value for an increasing
50        // subsequence of each length; it remains sorted in ascending order.
51        List<Integer> tails = new ArrayList<>();
52
53        for (int x : arr) {
54            // Binary search for the first element in 'tails' that is >= x.
55            int left = 0, right = tails.size();
56            while (left < right) {
57                int mid = (left + right) >>> 1;
58                if (tails.get(mid) >= x) {
59                    right = mid;
60                } else {
61                    left = mid + 1;
62                }
63            }
64
65            if (left == tails.size()) {
66                // x extends the longest subsequence found so far.
67                tails.add(x);
68            } else {
69                // Replace to keep the tail value minimal for that length.
70                tails.set(left, x);
71            }
72        }
73
74        return tails.size();
75    }
76}
77

1class Solution {
2public:
3    int longestSubsequence(vector<int>& nums) {
4        // Compute the length of the Longest Increasing Subsequence (strictly increasing)
5        // using the classic patience-sorting / binary-search technique in O(n log n).
6        auto computeLIS = [&](const vector<int>& arr) {
7            vector<int> tails; // tails[k] = smallest possible tail of an increasing subsequence of length k+1
8            for (int value : arr) {
9                // Find the first element >= value (strict LIS uses lower_bound).
10                auto it = lower_bound(tails.begin(), tails.end(), value);
11                if (it == tails.end()) {
12                    // value extends the longest subsequence so far.
13                    tails.push_back(value);
14                } else {
15                    // Replace to keep the tail as small as possible.
16                    *it = value;
17                }
18            }
19            return static_cast<int>(tails.size());
20        };
21
22        int ans = 0;
23
24        // Determine how many bits we need to inspect based on the maximum value.
25        int maxValue = ranges::max(nums);
26        int bitCount = (maxValue == 0) ? 0 : 32 - __builtin_clz(maxValue);
27
28        // For each bit position, gather the numbers whose i-th bit is set,
29        // then measure the LIS among those numbers. The best across all bits is the answer.
30        for (int i = 0; i < bitCount; ++i) {
31            vector<int> filtered;
32            ranges::copy_if(nums, back_inserter(filtered), [&](int x) {
33                return (x >> i) & 1; // keep numbers with the i-th bit set
34            });
35            ans = max(ans, computeLIS(filtered));
36        }
37
38        return ans;
39    }
40};
41

1/**
2 * Binary search equivalent of C++ std::lower_bound.
3 * Returns the index of the first element in `arr` that is >= `value`.
4 * If no such element exists, returns `arr.length`.
5 */
6function lowerBound(arr: number[], value: number): number {
7    let low = 0;
8    let high = arr.length;
9    while (low < high) {
10        const mid = (low + high) >> 1;
11        if (arr[mid] < value) {
12            // Element is too small; search the right half.
13            low = mid + 1;
14        } else {
15            // Element is a candidate; narrow toward the left.
16            high = mid;
17        }
18    }
19    return low;
20}
21
22/**
23 * Compute the length of the Longest Increasing Subsequence (strictly increasing)
24 * using the patience-sorting / binary-search technique in O(n log n).
25 */
26function computeLIS(arr: number[]): number {
27    // tails[k] = smallest possible tail of an increasing subsequence of length k + 1
28    const tails: number[] = [];
29    for (const value of arr) {
30        // Find the first element >= value (strict LIS uses lower_bound).
31        const idx = lowerBound(tails, value);
32        if (idx === tails.length) {
33            // value extends the longest subsequence so far.
34            tails.push(value);
35        } else {
36            // Replace to keep the tail as small as possible.
37            tails[idx] = value;
38        }
39    }
40    return tails.length;
41}
42
43/**
44 * For each bit position, gather the numbers whose i-th bit is set,
45 * then measure the LIS among those numbers. The best across all bits is the answer.
46 */
47function longestSubsequence(nums: number[]): number {
48    let ans = 0;
49
50    // Determine how many bits we need to inspect based on the maximum value.
51    const maxValue = Math.max(...nums);
52    // Number of significant bits; if maxValue is 0 there is nothing to inspect.
53    const bitCount = maxValue === 0 ? 0 : 32 - Math.clz32(maxValue);
54
55    for (let i = 0; i < bitCount; i++) {
56        // Keep only the numbers with the i-th bit set.
57        const filtered = nums.filter((x) => ((x >> i) & 1) === 1);
58        // Track the best LIS length found across all bit positions.
59        ans = Math.max(ans, computeLIS(filtered));
60    }
61
62    return ans;
63}
64