2.7 最長連續(xù)遞增序列 1. 題目描述 給定一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且連續(xù)的遞增序列。 示例 1: 輸入: [1,3,5,4,7] 輸出: 3 解釋: 最長連續(xù)遞增序列是 [1,3,5], 長度為3。 盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因為5和7在原數(shù)組里被4隔開。 示例 2: 輸入: [2,2,2,2,2] 輸出: 1 解釋: 最長連續(xù)遞增序列是 [2], 長度為1。注意：數(shù)組長度不會超過10000。 2. 分析與解法 這道題要求我們找出一個數(shù)組中最長的連續(xù)遞增序列。由于要求連續(xù)性，相比之前的“最長遞增子序列”問題，難度降低了很多。 解法一 我們可以使用一個計數(shù)器，當遇到較大的數(shù)字時，計數(shù)器自增1；當遇到較小的數(shù)字時，計數(shù)器重置為1。我們用一個變量cur來表示前一個數(shù)字，初始化為整型最大值，當前遍歷到的數(shù)字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; ??} }; ``` 解法二 下面這種方法的思路和上面的解法一樣，每次都和前面一個數(shù)字來比較，注意處理無法取到前一個數(shù)字的情況。 參考代碼： ```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