2026-06-01 Go语言算法精选：按位与结果非零的最长上升子序列

给定整数数组 nums，需从中选出严格递增的子序列，且子序列中所有元素的按位与（AND）结果非零。返回满足条件的最长子序列长度；若不存在则返回 0。子序列保持原数组的相对顺序（仅可删除元素）。数据范围：数组长度 ≤ 10⁵，元素值 ∈ [0, 10⁹]。

示例：nums = [5, 4, 7]，合法最长子序列为 [5, 7]，5 AND 7 = 5（非零），因此结果为 2。

本题源自力扣 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< 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):
				# 等价于 C++ 的 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 
#include 
#include 

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;
    return 0;
}