題目

??如題

思路

??核心思想是，維護一個數組ends，它記錄了長度為k的子序列的末尾元素的最小值。聽起來很抽象，我們不妨手動演示一遍整個過程。

??假設數組a={2,9,4,27,29,15,7}，令length表示當前找到的最長非下降子序列的長度。初始時length=1，ends[1]=2。

??i=1，length=2，ends[2]=9；

??i=2，length=2，ends[2]=4，原因是4比9更容易和后面的數構成非下降子序列；

??i=3，length=3，ends[3]=27；

??i=4，length=4，ends[4]=29；

??i=5，length=4，15能和ends[2]=4連接起來，并且它比ends[3]=27更容易和后面的數構成非下降子序列，因此ends[3]=15；

??i=6，length=4，end[3]=7。

??可以看到，整個算法就是找到ends中第一個大于當前數的位置。假設當前數為a[i]，找到的位置為t，說明ends[t-1]<=a[i]，那么a[i]可以和ends[t-1]連接起來，構成長度為i的子序列，同時ends[t]>a[i]，說明a[i]要比ends[t]更容易和后面的數構成子序列，因此進行替換。可以說，算法的思想是貪心加二分。

代碼

package com.iqiyi;public class Test {public static void main(String[] args){int[] array=new int[]{2,9,4,27,29,15,7};int[] ends=new int[array.length+1];ends[1]=array[0];int length=1;for(int i=1;i<array.length;i++){int low=1;int high=length;while(low<high){int mid=(low+high)/2;if(ends[mid]<=array[i])low=mid+1;elsehigh=mid;}if(ends[low]>array[i])ends[low]=array[i];else{length++;ends[length]=array[i];}}System.out.println(length);}
}
復制代碼