个人英文网站设计dw网页制作实例素材打包下载
一、题目描述
小明是蓝桥王国的勇士，他晋升为蓝桥骑士，于是他决定不断突破自我。
这天蓝桥首席骑士长给他安排了 N 个对手，他们的战力值分别为 a1,a2,...,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。
作为热血豪放的勇士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 N，表示对手的个数。
第二行包含 N 个整数 a1,a2,...,an，分别表示对手的战力值。
1≤N≤1e3，1≤ai≤1e9。
输出描述
输出一行整数表示答案。
输入输出样例
输入
6
1 4 3 2 5 6
输出
4二、 LIS算法介绍
最长递增子序列（LIS）算法详解及Java实现
最长递增子序列（Longest Increasing Subsequence，LIS）问题要求在一个无序的序列中找到最长的子序列，使得该子序列中的元素严格递增。以下是两种常见解法及其Java实现。方法一：动态规划（时间复杂度 O(n²)）
算法思路定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。初始化每个 dp[i] 为 1（每个元素本身构成一个长度为 1 的子序列）。
对于每个元素 nums[i]，遍历其之前的所有元素 nums[j]（j < i），若 nums[j] < nums[i]，则更新 dp[i] = max(dp[i], dp[j] + 1)。
最终结果为 dp 数组中的最大值。
import java.util.Arrays;public class LIS {public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) return 0;int[] dp = new int[nums.length];Arrays.fill(dp, 1);int maxLen = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLen = Math.max(maxLen, dp[i]);}return maxLen;} }
方法二：贪心 + 二分查找（时间复杂度 O(n log n)）
算法思路维护一个数组 tail，其中 tail[i] 表示长度为 i+1 的最长递增子序列的最小末尾元素。
遍历原数组，对于每个元素 num：
若 num 大于 tail 的最后一个元素，直接添加到 tail。
否则，使用二分查找在 tail 中找到第一个大于等于 num 的位置，替换为该元素。
最终 tail 的长度即为最长递增子序列的长度。
import java.util.ArrayList; import java.util.Collections;public class LIS {public int lengthOfLIS(int[] nums) {ArrayList<Integer> tail = new ArrayList<>();for (int num : nums) {if (tail.isEmpty() || num > tail.get(tail.size() - 1)) {tail.add(num);} else {int index = Collections.binarySearch(tail, num);index = (index < 0) ? -index - 1 : index;tail.set(index, num);}}return tail.size();} }
三、代码演示
import java.util.Scanner;public class Main { public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 读取输入的数组长度 nint[] a = new int[n]; // 创建数组 a 存储输入序列for (int i = 0; i < n; i++) {a[i] = scanner.nextInt(); // 逐个读取元素到数组 a}int[] dp = new int[n]; // 定义动态规划数组 dp，长度与输入数组一致int max = 1; // 初始化最长子序列长度为1（至少包含一个元素）for (int i = 0; i < n; i++) { // 外层循环遍历每个元素dp[i] = 1; // 关键修正：初始化 dp[i] 为1（每个元素自身构成长度为1的子序列）for (int j = 0; j < i; j++) { // 内层循环遍历 i 之前的所有元素 jif (a[i] > a[j]) { // 若当前元素 a[i] > a[j]，满足递增条件dp[i] = Math.max(dp[i], dp[j] + 1); // 更新 dp[i] 为更大的值（继承 j 的状态+1）}}max = Math.max(max, dp[i]); // 更新全局最大值}System.out.println(max); // 输出最长递增子序列的长度}
}示例验证
8
10 9 2 5 3 7 101 18
执行过程
初始化
dp 数组初始化为全1：[1, 1, 1, 1, 1, 1, 1, 1]。外层循环 i=0（元素10）
内层循环无 j < 0，直接跳过。
max 保持为1。
外层循环 i=1（元素9）
检查 j=0：9 < 10，不更新 dp[1]。
dp 保持为 [1, 1, ...]，max 仍为1。
外层循环 i=2（元素2）
检查 j=0：2 < 10 → 不更新。
检查 j=1：2 < 9 → 不更新。
dp 保持为 [1, 1, 1, ...]，max 仍为1。
外层循环 i=3（元素5）
检查 j=0：5 < 10 → 不更新。
检查 j=1：5 < 9 → 不更新。
检查 j=2：5 > 2 → dp[3] = max(1, 1+1) = 2。
dp 变为 [1, 1, 1, 2, ...]，max 更新为2。
外层循环 i=4（元素3）
检查 j=2：3 > 2 → dp[4] = max(1, 1+1) = 2。
dp 变为 [1, 1, 1, 2, 2, ...]，max 仍为2。
外层循环 i=5（元素7）
检查 j=2：7 > 2 → dp[5] = 1+1 = 2。
检查 j=3：7 > 5 → dp[5] = max(2, 2+1) = 3。
检查 j=4：7 > 3 → dp[5] = max(3, 2+1) = 3。
dp 变为 [1, 1, 1, 2, 2, 3, ...]，max 更新为3。
外层循环 i=6（元素101）
遍历所有 j < 6，找到最长子序列 [2,5,7]，长度3 → dp[6] = 3+1 = 4。
max 更新为4。
外层循环 i=7（元素18）
找到最长子序列 [2,5,7,18]，但 dp[7] = 4（与 dp[6] 相同）。
max 保持为4。