二级网站怎么做,wordpress 放大镜插件,潍坊网站建设报价,湖南seo推广多少钱题目#xff1a;小明是蓝桥王国的骑士#xff0c;他喜欢不断突破自我。
这天蓝桥国王给他安排了 N 个对手#xff0c;他们的战力值分别为 a1,a2,...,an#xff0c;且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战#xff0c;也可以选择避战。
身为高傲的骑士小明是蓝桥王国的骑士他喜欢不断突破自我。
这天蓝桥国王给他安排了 N 个对手他们的战力值分别为 a1,a2,...,an且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战也可以选择避战。
身为高傲的骑士小明从不走回头路且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 NN表示对手的个数。
第二行包含 N 个整数 a1,a2,...,an分别表示对手的战力值。
1≤N≤3×10^51≤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; in; i){enemy[i] scan.nextInt();//填充n个对手的战力值}int[] tail new int[n]; // tail[i] 存储长度为 i1 的上升子序列的最小结尾元素int length 0;//遍历n个对手for(int i 0; in; i){int left 0, right length; //声明数组的左右边界//二分查找while(leftright){ //左边边界 小于 右边边界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] 表示长度为 i1 的上升子序列的最小结尾元素。遍历每个对手使用 二分查找 找到第一个比 enemy[i] 大的位置替换或者扩展序列。最后输出的 tail[] 数组的长度就是 LIS 长度length 表示当前找到的最长递增子序列的长度。
