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

福大大架构师每日一题

发布于 2026-06-01 18:43:09

910

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<<bit) != 0 {
                // lower_bound 的等价实现
                idx := sort.SearchInts(list, x)
                if idx == len(list) {
                    list = append(list, x)
                } else {
                    list[idx] = x
                }
            }
        }
        iflen(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++完整代码如下：

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int ans = 0;
        for (int bit = 0; bit < 32; bit++) {
            vector<int> 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<int> nums = {5, 4, 7};
    int result = sol.longestSubsequence(nums);
    cout << result << endl;
    return0;
}