人工智能AI面试题-2.7 最长连续递增序列

2.7 最长连续递增序列 1. 题目描述 给定一个未经排序的整数数组，找到最长且连续的递增序列。 示例 1: 输入: [1,3,5,4,7] 输出: 3 解释: 最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 示例 2: 输入: [2,2,2,2,2] 输出: 1 解释: 最长连续递增序列是 [2], 长度为1。注意：数组长度不会超过10000。 2. 分析与解法 这道题要求我们找出一个数组中最长的连续递增序列。由于要求连续性，相比之前的“最长递增子序列”问题，难度降低了很多。 解法一 我们可以使用一个计数器，当遇到较大的数字时，计数器自增1；当遇到较小的数字时，计数器重置为1。我们用一个变量cur来表示前一个数字，初始化为整型最大值，当前遍历到的数字num就与cur比较，每次用cnt来更新结果res。 参考代码： ```cpp class Solution { public:   int findLengthOfLCIS(vector& nums) {     int res = 0, cnt = 0, cur = INT_MAX;     for (int num : nums) {       if (num > cur) ++cnt;       else cnt = 1;       res = max(res, cnt);       cur = num;     }     return res;   } }; ``` 解法二 下面这种方法的思路和上面的解法一样，每次都和前面一个数字来比较，注意处理无法取到前一个数字的情况。 参考代码： ```cpp class Solution { public:   int findLengthOfLCIS(vector& nums) {     int res = 0, cnt = 0, n = nums.size();     for (int i = 0; i < n; ++i) {       if (i == 0 || nums[i - 1] < nums[i]) res = max(res, ++cnt);       else cnt = 1;     }     return res;   } }; ``` 类似题目： Number of Longest Increasing Subsequence