題目：小明是藍橋王國的騎士，他喜歡不斷突破自我。
這天藍橋國王給他安排了?N?個對手，他們的戰力值分別為?a1,a2,...,an，且按順序阻擋在小明的前方。對于這些對手小明可以選擇挑戰，也可以選擇避戰。
身為高傲的騎士，小明從不走回頭路，且只愿意挑戰戰力值越來越高的對手。
請你算算小明最多會挑戰多少名對手。
輸入描述
輸入第一行包含一個整數?NN，表示對手的個數。
第二行包含?N?個整數?a1,a2,...,an?，分別表示對手的戰力值。
1≤N≤3×10^5，1≤ai?≤10^9。
輸出描述
輸出一行整數表示答案。
輸入輸出樣例
示例 1
輸入
6
1 4 2 2 5 6
輸出
4解題思路＋代碼：
代碼：
import java.util.Scanner;
import java.util.Arrays;
// 1:無需package
// 2: 類名必須Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt(); // n個對手int[] enemy = new int[n]; //防止數組下標越界for(int i = 0; i<n; i++){enemy[i] = scan.nextInt();//填充n個對手的戰力值}int[] tail = new int[n]; // tail[i] 存儲長度為 i+1 的上升子序列的最小結尾元素int length = 0;//遍歷n個對手for(int i = 0; i<n; i++){int left = 0, right = length; //聲明數組的左右邊界//二分查找while(left<right){ //左邊邊界 小于 右邊邊界int mid = (left + right) / 2; if(tail[mid] < enemy[i]){left = mid + 1; //左邊邊界右移}else{right = mid; //右邊邊界左移}}// 更新當前長度的最小結尾tail[left] = enemy[i]; // 如果 a[i] 比所有 tail 中的值都大，則擴展長度if(left == length){length++;}}System.out.println(length);scan.close();}
}?總結：這時一道LIS（最長上升子序列）問題，必須采用 貪心 + 二分查找的算法來解答。LIS的核心是必須按照原順序選擇對手，不能隨意調整順序，定義 tail[] 數組，tail[i] 表示長度為 i+1 的上升子序列的最小結尾元素。遍歷每個對手，使用 二分查找 找到第一個比 enemy[i] 大的位置，替換或者擴展序列。最后輸出的?tail[] 數組的長度就是 LIS 長度（length 表示當前找到的最長遞增子序列的長度）。
