给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

 

首先是O(n^2)的算法，就是用一个数组a来存储到某个位置的最长上升子序列的长度，最后返回最大值。要求出每个点的a [ i ]，就必须把 i 前面的点都扫描一遍，所以需要时间O(n^2)。

int lengthOfLIS(int* nums, int numsSize) {    int i,j,rs=0;    int *a=(int *)malloc(sizeof(int)*numsSize);    for(i=0;i
     
      nums[j]&&a[j]+1>a[i])                a[i]=a[j]+1;        if(rs
     

然后是大佬的解法，说实话这段代码的可读性有点差，但也可能是我太蠢了。。。

算法的主要思路是维护一个变动的最长上升子序列。用数组d来存储这个变动的最长上升子序列，这个数组里每新增一个数，就确定了一个暂时的最长上升子序列，只要这个数组的最后一个数没变，已确定好的最长上升子序列就没变，所以更新已添加的节点不会对结果有任何影响。每扫描一个点，如果这个点比d里所有的数大，就把这个点扩充到d里，否则就把d里刚好比它大的数换成它，以便寻找后面的上升子序列。

int lengthOfLIS(int* n, int ns){    int i=0, j=0, c=0;    int s=0, e=0, m=0;    int *d = malloc(ns * sizeof(int));    if (ns < 1)        return 0;    for (i=1, c=1, d[0]=n[0]; i
     
       n[i])                e = m - 1;            else                s = m + 1;        }        d[s] = n[i];        c = s+1 > c ? s+1 : c;    }    return c;}