最长上升子序列贪心 java代码

以下是最长上升子序列的贪心算法的Java代码：

public static int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int res = 0;
    for (int num : nums) {
        int i = 0, j = res;
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (tails[mid] < num) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        tails[i] = num;
        if (res == j) res++;
    }
    return res;
}

算法思路：

1. 创建一个长度为 nums.length 的数组 tails，tails[i] 表示长度为 i 的上升子序列的末尾元素的最小值。
2. 遍历 nums 数组，对于每个元素 num，将其二分插入 tails 数组中。
3. 如果 num 大于 tails 数组的最后一个元素，那么将 num 放到 tails 数组的末尾。
4. 如果 num 在 tails 数组中的位置 i 大于 0，那么 tails[i-1] < num < tails[i]，则用 num 替换 tails[i]，使得 tails 数组中的元素依旧保持上升的顺序。
5. 如果 num 在 tails 数组中的位置 i 等于 0，那么 tails[i-1] 不存在，num 就是新的最小值，将其放到 tails 数组的开头。
6. 最终 tails 数组的长度就是最长上升子序列的长度。

时间复杂度：O(nlogn)，其中 n 是 nums 数组的长度。tails 数组的长度不超过 n，因此外层循环的时间复杂度是 O(n)，内层循环的时间复杂度是 O(logn)。总时间复杂度为 O(nlogn)。