给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路：emmm，还没学动态规划，就看了一下官方思路写了一下，贪心和二分查找，二分查找主要用于优化速率。用一个dp数组保存最长子序列，从第一个数据开始，如果第二个数据比第一个数据小，如果大，就直接放到后边，然后第二个数据就顶替第一个数据，如果后边有数据，在dp数组中间，则这个数据就直接把刚好比它大的那个数据顶替掉，emmmm说不清楚。。。
直接上实例：
首先dp[0] = 10 然后发现nums[1]<dp[0]，所以直接用nums[1]作为dp[0]重新开始，遇到nums[2]<dp[0],同理，遇到nums[3] = 5,放到后边，遇到nums[4] = 3,它大于2小于5，直接顶替5，以此类推
dp数组中的元素变化：
dp[numsSize] = 10
dp[numsSize] = 9
dp[numsSize] = 2
dp[numsSize] = 2 5
dp[numsSize] = 2 3
dp[numsSize] = 2 3 7
dp[numsSize] = 2 3 7 101
dp[numsSize] = 2 3 18 101
ok ok 返回长度即可。
int lengthOfLIS(int* nums, int numsSize)
{
if(numsSize == 0)
return 0;
int dp[numsSize];
int p = -1;
dp[++p] = nums[0];
for(int i=0; i<numsSize; i++)
{
if(nums[i] > dp[p])
{
dp[++p] = nums[i];
}
else //进行二分查找法
{
int low = 0; //指向头部
int high = p; //指向尾部
int ptr = 0;
while(low <= high)
{
int mid = (high+low)/2; //指向中间
if(nums[i] > dp[mid])
{
ptr = mid;
low = mid+1;
}
else if(nums[i] <= dp[mid])
{
high = mid-1;
}
}
if(dp[ptr] >= nums[i])
{
dp[ptr] = nums[i];
}
else
{
dp[ptr+1] = nums[i];
}
}
}
return p+1;
}
贪心+二分查找：最长上升子序列（3.14 leetcode每日打卡）
原文：https://www.cnblogs.com/ZhengLijie/p/12493638.html
