主题给出数组arr，返回arr的最长增加部分序列
示例： ARR=[2、1、5、3、6、4、8、9、7]，返回的最长递增子序列为[1、3、4、8、9]
要求： arr长度为n时，请实现时间复杂度为o(nlogn )的方法。
分析该问题也是经典的动态规划，常规动态规划时间复杂度为o(n^2)；
加上二分钟，可以将动态计划优化为o(nlogn )。
解法1o(n )2)的动态计划理解问题后，假设状态由数组的当前位置I决定返回值，则DP ) I )表示arr ) 0…I )的最长增加子串
dp[i]=max{dp[i]，DP[j]1}(0=Jiarr[I]arr[j] ) )
//DPO(n^2) int*getDP1(intarr[]，int长度) { int* dp=new int[length]； for(intI=0； ilength； I ) { dp[i]=1； for(intj=0； ji； j ) {DP[I]=max(DP[I]，dp[j] 1)； } }返回DP； }需要求出增加数组时，请执行以下步骤。
首先，arr从右向左找到最大值，根据该最大值向前递归移动，满足以下条件：
像arr[j] arr[i] dp[i]=dp[j] 1这样的递归会产生特殊情况，要找到所有情况就必须添加另一个循环。
解法2o(nlogn )的动态规划我们在上述搜索过程中，总是比较arr，可以用时间将增量序列保存在数组中，以换取空间，对该序列进行二分搜索。
以下是示例。
arr=[ 2，1，5，3，6，4，8，9，7 ]
采用ends[length 1]作为升序排列，right记录排列的长度
遍历arr数组，如果arr[i]查询arr[i]在ends中的位置arr[i]大于ends[right]，则将arr[i]直接添加到ends中，如果与增量不匹配，则在平分时
int*getDP2(intarr[]，int length ) { int* dp=new int[length 1]； int* ends=new int[length 1]； ends[0]=arr[0]； dp[0]=1； int right=0； int l=0； int r=0； int m=0； for(intI=1； ilength； I () L=0； r=right； wile(L=R ) ) m=L ) R-L )/2； if(ARR[I]ends[m] ) { l=m 1； (else ) r=m-1； }right=max(L，right )； ends[l]=arr[i]； dp[i]=l 1； }返回DP； } Conclusion主题动态规划优化采用两点优化，采用空间交换时间；
以前也有路径压缩，降低了空间复杂度的主题机器人到达指定位置的方法的数量