用Java计算最长递增子序列，时间复杂度未nlogn

您好，我可以为您提供代码实现，用 Java 计算最长递增子序列，时间复杂度为 O(nlogn)。

请参考以下代码：

public static int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;

    for (int x : nums) {
        int i = 0, j = size;
        while (i != j) {
            int m = (i + j) / 2;
            if (tails[m] < x) {
                i = m + 1;
            } else {
                j = m;
            }
        }
        tails[i] = x;
        if (i == size) ++size;
    }

    return size;
}

该代码使用了一种称为二分查找（Binary Search）的方法，将时间复杂度优化到了 O(nlogn)。此方法的思想是维护一个 tails 数组，它始终存储着最长递增子序列。我们遍历整个 nums 数组，对于每个元素，在 tails 中寻找位置并更新为当前元素。如果当前元素是比所有 tails 中的元素都大的，则直接将当前元素放入 tails 数组中。最终，tails 数组的长度就是最长递增子序列的长度。

希望这能帮助到您，如果您有任何其他问题，随时可以问我。