leetcode300. 最長遞增子序列

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/longest-increasing-subsequence

題目描述

給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度。
子序列 是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

示例 1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：
輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：
輸入：nums = [7,7,7,7,7,7,7]
輸出：1

提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

進(jìn)階：
你能將算法的時間復(fù)雜度降低到 O(n log(n)) 嗎?

解題思路

我們設(shè)計動態(tài)規(guī)劃算法，不是需要一個 dp 數(shù)組嗎？我們可以假設(shè) dp[0…i-1] 都已經(jīng)被算出來了，然后問自己：怎么通過這些結(jié)果算出 dp[i]？
根據(jù)題目的定義,我們很容易得出base case dp[i] = 1;任何位置本身的長度可以先初始化為1.
我們再看怎么求出具體值,用圖來演示:

知道dp[3] = 3,時,怎么求dp[4] 呢,4 位置的數(shù)字從0 位置開始比較到3位置,
如果4位置的數(shù)字比3位置的數(shù)字大,那么dp[4] = 1 + dp[3];
知道這個過程我們就可以寫出dp算法了.

代碼演示:

	/**
	*  最長遞增子序列 可以直接復(fù)制進(jìn)力扣測試
	*/
   int lengthOfLIS(int[] nums) {
       int N = nums.length;
       //動態(tài)規(guī)劃表
       int[]dp = new int[N];
       for(int i = 0; i < N; i++){
       //base case 每個位置本身長度
           dp[i] = 1;
           for(int j = 0;j < i; j++){
           // i 位置依次向前比 ,比j 位置大,就是 1 + dp[i]
           // 根據(jù)不同j位置上的數(shù),來更新最大值
               if(nums[i] > nums[j]){
                  dp[i] = Math.max(dp[i],1 + dp[j]);  
               }
               
           }
       }
       int res = 0;
       //取出 dp表中的最大值 就是我們要的答案.
       for (int i = 0; i < dp.length;i++){
           res = Math.max(res,dp[i]);
       }
       return res;
    }

二分法改進(jìn)(N * logN)

	/**
	*  最長遞增子序列 可以直接復(fù)制進(jìn)力扣測試
	*/
   int lengthOfLIS(int[] nums) {
        int N = nums.length;
        int[] ends = new int[N];
        int pies = 0;
        for(int i = 0 ; i < nums.length;i++){
            int cur = nums[i];
            int L = 0;
            int R = pies;
            while(L < R){
                int mid = (L + R) / 2;
                if(ends[mid] >= cur){
                    R = mid;
                }else{
                    L = mid + 1;
                }
            }

            if(L == pies){
                pies++;
            }
            ends[L] = cur;
        }

        return pies;
    }

動態(tài)規(guī)劃專題

leetcode494. 目標(biāo)和

leetcode337. 打家劫舍 III

leetcode213. 打家劫舍 II

leetcode198. 打家劫舍

leetcode174. 地下城游戲

leetcode688. 騎士在棋盤上的概率文章來源地址http://www.zghlxwxcb.cn/news/detail-606786.html

到了這里，關(guān)于leetcode300. 最長遞增子序列(動態(tài)規(guī)劃-java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！