生成手机版网站,哈尔滨企业网站制作,色彩搭配比较好的网站,怎么建自己的公众号一、题目描述
小明是蓝桥王国的勇士#xff0c;他晋升为蓝桥骑士#xff0c;于是他决定不断突破自我。
这天蓝桥首席骑士长给他安排了 N 个对手#xff0c;他们的战力值分别为 a1,a2,...,an#xff0c;且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战#xf…一、题目描述
小明是蓝桥王国的勇士他晋升为蓝桥骑士于是他决定不断突破自我。
这天蓝桥首席骑士长给他安排了 N 个对手他们的战力值分别为 a1,a2,...,an且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战也可以选择避战。
作为热血豪放的勇士小明从不走回头路且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 N表示对手的个数。
第二行包含 N 个整数 a1,a2,...,an分别表示对手的战力值。
1≤N≤1e31≤ai≤1e9。
输出描述
输出一行整数表示答案。
输入输出样例
输入
6
1 4 3 2 5 6输出 4 二、 LIS算法介绍 最长递增子序列LIS算法详解及Java实现 最长递增子序列Longest Increasing SubsequenceLIS问题要求在一个无序的序列中找到最长的子序列使得该子序列中的元素严格递增。以下是两种常见解法及其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] 表示长度为 i1 的最长递增子序列的最小末尾元素。 遍历原数组对于每个元素 num 若 num 大于 tail 的最后一个元素直接添加到 tail。 否则使用二分查找在 tail 中找到第一个大于等于 num 的位置替换为该元素。 最终 tail 的长度即为最长递增子序列的长度。 import java.util.ArrayList;
import java.util.Collections;public class LIS {public int lengthOfLIS(int[] nums) {ArrayListInteger 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]。 外层循环 i0元素10 内层循环无 j 0直接跳过。 max 保持为1。 外层循环 i1元素9 检查 j09 10不更新 dp[1]。 dp 保持为 [1, 1, ...]max 仍为1。 外层循环 i2元素2 检查 j02 10 → 不更新。 检查 j12 9 → 不更新。 dp 保持为 [1, 1, 1, ...]max 仍为1。 外层循环 i3元素5 检查 j05 10 → 不更新。 检查 j15 9 → 不更新。 检查 j25 2 → dp[3] max(1, 11) 2。 dp 变为 [1, 1, 1, 2, ...]max 更新为2。 外层循环 i4元素3 检查 j23 2 → dp[4] max(1, 11) 2。 dp 变为 [1, 1, 1, 2, 2, ...]max 仍为2。 外层循环 i5元素7 检查 j27 2 → dp[5] 11 2。 检查 j37 5 → dp[5] max(2, 21) 3。 检查 j47 3 → dp[5] max(3, 21) 3。 dp 变为 [1, 1, 1, 2, 2, 3, ...]max 更新为3。 外层循环 i6元素101 遍历所有 j 6找到最长子序列 [2,5,7]长度3 → dp[6] 31 4。 max 更新为4。 外层循环 i7元素18 找到最长子序列 [2,5,7,18]但 dp[7] 4与 dp[6] 相同。 max 保持为4。
