当前位置：首页 > java >正文

华为高频算法题：最长连续递增子序列（Longest Continuous Increasing Subsequence）

java 2025/7/27 7:26:35

文章目录

- 前言
- 题目描述（华为校招真题）
- 解题思路分析
- Java 实现代码
- 单元测试代码
- 结语

前言

在各大互联网公司的算法面试中，数组类题目一直是考察的重点，尤其是对于应届生和初级工程师的面试来说更是常见题型。华为作为国内顶尖的科技企业，在校招和社招中也经常考察这类基础但极具代表性的题目。本题“最长连续递增子序列”是一道典型的数组遍历与状态维护问题，虽然难度适中，但却能很好地考察候选人对边界条件的处理能力、逻辑思维的严谨性以及代码的简洁性和可读性。

在这里插入图片描述

题目描述（华为校招真题）

给定一个无重复元素的整数数组 nums，返回最长连续递增子序列的长度。
连续递增子序列定义为：数组中连续的一段元素 [i, i+1, i+2, …, j]，满足 nums[i] < nums[i+1] < … < nums[j]。
示例：

输入: nums = [1,3,5,4,7]
输出: 3
解释: 最长的连续递增子序列是 [1, 3, 5]，长度为 3。输入: nums = [2,2,2,2]
输出: 1
解释: 每个元素都是独立的递增序列。

解题思路分析

我们可以采用一次遍历的方式解决该问题
1、初始化两个变量maxLength（记录最长递增序列的长度）、currentLength(当前递增序列的长度)；
2、从第二个元素开始遍历数组如果当前元素大于前一个元素，则 currentLength++，否则重置 currentLength = 1，每次更新 maxLength；
3、算法时间复杂度：O(n)，空间复杂度：O(1)

Java 实现代码

/*** LongestContinuousIncreasingSubsequence* @author senfel* @version 1.0* @date 2025/7/23 11:54*/
public class LongestContinuousIncreasingSubsequence {/*** findLengthOfLCIS* @param nums* @author senfel* @date 2025/7/23 11:55 * @return int*/public int findLengthOfLCIS(int[] nums) {// 验证是否为空if (nums == null || nums.length == 0) {return 0;}//最长递增序列的长度int maxLength = 1;//当前递增序列的长度int currentLength = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) {currentLength++;maxLength = Math.max(maxLength, currentLength);} else {currentLength = 1;}}return maxLength;}
}

单元测试代码

/*** LongestContinuousIncreasingSubsequenceTest* @author senfel* @version 1.0* @date 2025/7/23 12:02*/
public class LongestContinuousIncreasingSubsequenceTest {private final LongestContinuousIncreasingSubsequence solution = new LongestContinuousIncreasingSubsequence();@Testpublic void testBasicCase1() {int[] nums = {1, 3, 5, 4, 7};assertEquals(3, solution.findLengthOfLCIS(nums));}@Testpublic void testAllSameElements() {int[] nums = {2, 2, 2, 2};assertEquals(1, solution.findLengthOfLCIS(nums));}@Testpublic void testEmptyArray() {int[] nums = {};assertEquals(0, solution.findLengthOfLCIS(nums));}@Testpublic void testSingleElement() {int[] nums = {5};assertEquals(1, solution.findLengthOfLCIS(nums));}@Testpublic void testFullyIncreasing() {int[] nums = {1, 2, 3, 4, 5};assertEquals(5, solution.findLengthOfLCIS(nums));}@Testpublic void testMultipleSegments() {int[] nums = {1, 2, 5, 3, 4, 6, 2, 3, 4, 5};assertEquals(4, solution.findLengthOfLCIS(nums));}
}