最長連續遞增序列解題思路

題目

給定一個未經排序的整數數組，找到最長且 連續遞增的子序列，并傳回該序列的長度。

連續遞增的子序列 可以由兩個下标 l 和 r（l < r）确定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那麼子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續遞增子序列。

示例1：

輸入：nums = [1,3,5,4,7] 輸出：3 解釋：最長連續遞增序列是 [1,3,5], 長度為3。 盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續的，因為 5 和 7 在原數組裡被 4 隔開。

示例2：

輸入：nums = [2,2,2,2,2] 輸出：1 解釋：最長連續遞增序列是 [2], 長度為1。

提示：

• 0 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

解題思路

根據題意，本題可用動态規劃的方式來求解。

第一步，确定dp數組以及下标的含義：

dp[i]：以下标i為結尾的數組的連續遞增的子序列長度為dp[i]。

第二步，确定遞推公式：

如果 nums[i + 1] > nums[i]，那麼以 i+1 為結尾的數組的連續遞增的子序列長度一定等于 以 i 為結尾的數組的連續遞增的子序列長度 + 1 。是以可以得出遞推公式為：dp[i + 1] = dp[i] + 1;

第三步，dp 數組初始化：

連續遞增的子序列長度最少是 1， 是以 dp 數組應該初始化為 1。

第四步，确定周遊順序：

代碼實作

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length == 0){
            return 0;
        };
        int count = 1;
        int len = nums.length;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            dp[i] = 1;
        }

        for(int i = 0; i < len - 1; i++){
            if(nums[i+1] > nums[i]){
                dp[i+1] = dp[i] + 1;
            }
            if(dp[i+1] > count) count = dp[i+1];
        }

        return count;
    }
}      

最後

• 時間複雜度：O(n)，其中 n 是數組 nums 的長度。
• 空間複雜度：O(1)。

• ​​# UE4：來為我們的角色制作一個血條吧​​
• ​​使用 Google Breakpad 來助力解決程式崩潰​​
• ​​UE4 多人遊戲伺服器探索​​
• ​​使用虛幻引擎自動化工具實作自動化部署​​
• ​​如何在 UE4 中制作一扇自動開啟的大門​​
• ​​如何在 UE4 中用代碼去控制角色移動​​
• ​​如何給 UE4 場景添加遊戲角色​​
• ​​UE4：Android 平台開發實踐指南​​
• ​​UE4 開發避坑指南（持續更新）​​
• ​​新年開工啦，放個小煙花慶祝一下​​
• ​​聊聊與蘋果稽核員的愛恨情仇(下)​​
• ​​聊聊與蘋果稽核員的愛恨情仇(上)​​
• ​​一名普通工具人的 2021 | 2021年終總結​​
• ​​二叉樹刷題總結：二叉搜尋樹的屬性​​
• ​​二叉樹總結：二叉樹的屬性​​
• ​​二叉樹總結：二叉樹的修改與構造​​
• ​​StoreKit2 有這麼香？嗯，我試過了，真香​​
• ​​看完這篇文章，再也不怕面試官問我如何構造二叉樹啦！​​
• ​​那幫做遊戲的又想讓大家氪金，太壞了！​​
• ​​手把手帶你撸一個網易雲音樂首頁 | 适配篇​​
• ​​手把手帶你撸一個網易雲音樂首頁（三）​​
• ​​手把手帶你撸一個網易雲音樂首頁（二）​​
• ​​手把手帶你撸一個網易雲音樂首頁（一）​​
• ​​代碼要寫注釋嗎？寫你就輸了​​
• ​​Codable釋出這麼久我就不學，摸魚爽歪歪，哎~就是玩兒​​
• ​​iOS 優雅的處理網絡資料，你真的會嗎？不如看看這篇​​
• ​​UICollectionView 自定義布局！看這篇就夠了​​

1. 關注公衆号--- HelloWorld傑少