3825. 最长严格递增且按位与非零的子序列

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 0;
        
        // 对每一位进行枚举
        for (int bit = 0; bit < 31; bit++) {
            vector<int> filtered;
            // 筛选出第bit位为1的元素
            for (int num : nums) {
                if (num & (1 << bit)) {
                    filtered.push_back(num);
                }
            }
            
            if (filtered.empty()) continue;
            
            // 计算LIS
            vector<int> lis;
            for (int num : filtered) {
                auto it = lower_bound(lis.begin(), lis.end(), num);
                if (it == lis.end()) {
                    lis.push_back(num);
                } else {
                    *it = num;
                }
            }
            
            maxLen = max(maxLen, (int)lis.size());
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        max_len = 0
        
        # 对每一位进行枚举
        for bit in range(31):
            # 筛选出第bit位为1的元素
            filtered = [num for num in nums if num & (1 << bit)]
            
            if not filtered:
                continue
            
            # 计算LIS
            from bisect import bisect_left
            lis = []
            for num in filtered:
                pos = bisect_left(lis, num)
                if pos == len(lis):
                    lis.append(num)
                else:
                    lis[pos] = num
            
            max_len = max(max_len, len(lis))
        
        return max_len

public class Solution {
    public int LongestSubsequence(int[] nums) {
        int maxLen = 0;
        
        // 对每一位进行枚举
        for (int bit = 0; bit < 31; bit++) {
            var filtered = new List<int>();
            // 筛选出第bit位为1的元素
            foreach (int num in nums) {
                if ((num & (1 << bit)) != 0) {
                    filtered.Add(num);
                }
            }
            
            if (filtered.Count == 0) continue;
            
            // 计算LIS
            var lis = new List<int>();
            foreach (int num in filtered) {
                int pos = BinarySearch(lis, num);
                if (pos == lis.Count) {
                    lis.Add(num);
                } else {
                    lis[pos] = num;
                }
            }
            
            maxLen = Math.Max(maxLen, lis.Count);
        }
        
        return maxLen;
    }
    
    private int BinarySearch(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var longestSubsequence = function(nums) {
    const n = nums.length;
    const memo = new Map();
    
    function dp(i, mask) {
        if (i === n) return 0;
        
        const key = `${i},${mask}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = dp(i + 1, mask);
        
        if (mask === -1 || nums[i] > nums[mask]) {
            const newMask = mask === -1 ? 0 : memo.get(`and,${mask},${i}`) || (memo.get(`and,${mask},${i}`) = nums[mask] & nums[i]);
            const andValue = mask === -1 ? nums[i] : newMask;
            
            if (andValue !== 0) {
                result = Math.max(result, 1 + dp(i + 1, i));
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    let maxLen = 0;
    const dp2 = new Map();
    
    for (let i = 0; i < n; i++) {
        const states = new Map();
        
        for (let [prevAnd, len] of dp2) {
            const newAnd = prevAnd & nums[i];
            if (newAnd !== 0) {
                states.set(newAnd, Math.max(states.get(newAnd) || 0, len + 1));
            }
        }
        
        if (nums[i] !== 0) {
            states.set(nums[i], Math.max(states.get(nums[i]) || 0, 1));
        }
        
        for (let [and, len] of states) {
            dp2.set(and, Math.max(dp2.get(and) || 0, len));
            maxLen = Math.max(maxLen, len);
        }
    }
    
    return maxLen;
};