使用动态规划和贪心两种算法

最长上升子序列问题，就是对于一个有顺序的数列， 从中按顺序选择的尽可能元素 (可以不连续) 构成的新数列是单调递增的.

最长上升子序列问题在许多与图论，算法，随机矩阵理论， 表示论相关的研究都会涉及， 比如排列图中的最大团是由 ' 定义该图的排列中最长的递减子序列 ' 定义的， 求最长的递减子序列在计算复杂度上 (通过对所有数取它的负数) 等同于求最长的递增子序列. 因此，最长递增子序列算法可用于有效地解决排列图中的分团问题

动态规划

动态规划其实非常好想到。设 f [i] 为以第 i 个数字结尾的最长上升子序列， 则 for j in range(1, i): if nums[i] > nums[j]: f[i] = max(f[j] + 1, f[i]).

贪心

动态规划的复杂度还是有点高，有没有什么更好的办法。毕竟理论上， 我只要扫描一遍数组，这个序列长度就是一定的.

首先考虑的肯定是贪心。要想得到最长上升子序列， 这个序列的上升速度必须有，但是要尽可能的慢， 这样子后面才有更大的上升空间。要想让上升速度慢， 每次加到序列末尾的数字必须尽可能的小。当然，也必须大于前一个数字.

那我们就需要记录一下这个最小值方便以后更新. 因为序列是一个数一个数添加起来的，所以每个长度的末尾最小值都需要记录. 把这个数组叫做 tail_min.

从定义可以得到: tail_min 是单调增的。可以用反证法证明.

接下来的事情就简单了， 我们一次遍历原数组中的每个元素更新 tail_min 里的值. 为了方便查找当前最长的序列，再维护一个 longest_length 变量.

这样，对于每个数 num, 如果 num > tail_min [longest_length], 则 tail_min[++longest_length] = num.

否则， 查找满足 for i in range(1, longest_length): tail_min[i-1] < num < tail_min[i] 的 i, 令 tail_min[i] = num. 这里可以使用二分查找优化速度.

最后输出 longest_length 就可以啦。时间复杂度是 O (nlogn), 空间复杂度为 O (n)

def longest_increasing_subsequence(nums):
    tail_min = [ math.inf for _ in range(len(nums)+1)]
    tail_min[1] = nums[0]
    longest_length = 1
    for num in nums:
        if num > tail_min[longest_length]:
            longest_length += 1
            tail_min[longest_length] = num
        else:
            left = 1
            right = longest_length
            left_to_pos = 0
            while left <= right:
                mid = (right - left) // 2 + left
                if num <= tail_min[mid]:
                    right = mid - 1
                else:
                    left_to_pos = mid
                    left = mid + 1
            tail_min[left_to_pos + 1]  = num
    return longest_length
unsigned long long int longest_increasing_subsequence(
    unsigned long long int nums[],
    size_t, size){
    unsigned long long int tail_min[size+1];
    memset(tail_min, 0, sizeof(tail_min))
    tail_min[1] = num[0];
    size_t longest_length = 1;
    for(size_t i = 0; i < size; i++){
        if(nums[i] > tail_min[longest_length])
            tail_min[++longest_length] = nums[i];
        else {
            size_t left = 1;
            size_t right = longest_length;
            size_t left_to_pos = 0;
            while(left <= right){
                size_t mid = (right - left) >> 1 + left;
                if(nums[i] <= tail_min[mid])
                    right = mid - 1;
                else{
                    left_to_pos = mid;
                    left = mid + 1;
                }
            }
            tail_min[left_to_pos+1] = nums[i];
        }
    }
    return longest_length;
}