2026-06-01：按位与结果非零的最长上升子序列。用go语言，给定一个整数数组 nums。你需要在其中选择一个子序列，使它的元素严格递增，并

2026-06-01：按位与结果非零的最长上升子序列。用go语言，给定一个整数数组 nums。你需要在其中选择一个子序列，使它的元素严格递增，并且把该子序列所有元素做按位与运算（AND），最后得到的结果必须是非零。要求该子序列的长度尽可能大，并返回这个最大长度；如果不存在满足条件的子序列，就返回 0。子序列要求保持原数组的相对顺序，只能删除元素，不能改变顺序。

1 <= nums.length <= 100000。

0 <= nums[i] <= 1000000000。

输入： nums = [5,4,7]。

输出： 2。

解释：

一个最长严格递增子序列是 [5, 7]。按位与的结果是 5 AND 7 = 5，结果为非零。

题目来自力扣3825。

大体步骤如下：Go完整代码如下：

package main

import (
    "fmt"
    "sort"
)

func longestSubsequence(nums []int)int {
    ans := 0
    for bit := 0; bit < 32; bit++ {
        list := []int{}
        for _, x := range nums {
            if x&(1< 

0 
{ 

 

// lower_bound 的等价实现 

 
idx := sort.SearchInts(list, x) 

 

if 
idx ==  
len 
(list) { 

 
list =  
append 
(list, x) 

 
}  
else 
{ 

 
list[idx] = x 

 
} 

 
} 

 
} 

 

if 
len 
(list) > ans { 

 
ans =  
len 
(list) 

 
} 

 
} 

 

return 
ans 

 
} 

 

 
func main() 
{ 

 
nums := [] 
int 
{ 
5 
,  
4 
,  
7 
} 

 
result := longestSubsequence(nums) 

 
fmt.Println(result) 

 
} 

 

Python完整代码如下：

# -*-coding:utf-8-*-

from bisect import bisect_left

def longestSubsequence(nums):
    ans = 0
    for bit in range(32):
        lst = []
        for x in nums:
            if x & (1 << bit):
                # lower_bound 的等价实现
                idx = bisect_left(lst, x)
                if idx == len(lst):
                    lst.append(x)
                else:
                    lst[idx] = x
        ans = max(ans, len(lst))
    return ans

if __name__ == "__main__":
    nums = [5, 4, 7]
    result = longestSubsequence(nums)
    print(result)

C++完整代码如下：

  

   

using namespace std;

class Solution {
public:
    int longestSubsequence(vector& nums) {
        int ans = 0;
        for (int bit = 0; bit < 32; bit++) {
            vector list;
            for (int x : nums) {
                if (x & (1 << bit)) {
                    // lower_bound 的等价实现
                    auto idx = lower_bound(list.begin(), list.end(), x);
                    if (idx == list.end()) {
                        list.push_back(x);
                    } else {
                        *idx = x;
                    }
                }
            }
            if ((int)list.size() > ans) {
                ans = (int)list.size();
            }
        }
        return ans;
    }
};

int main() {
    Solution sol;
    vector nums = {5, 4, 7};
    int result = sol.longestSubsequence(nums);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。