300. 最長(zhǎng)遞增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/

給你一個(gè)整數(shù)數(shù)組nums，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。子序列是由數(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，解釋：最長(zhǎng)遞增子序列是[2,3,7,101]，因此長(zhǎng)度為4。
2. 輸入：nums = [0,1,0,3,2,3]，輸出：4。
3. 輸入：nums = [7,7,7,7,7,7,7]，輸出：1。

提示：1 <= nums.length <= 2500，-10^4 <= nums[i] <= 10^4。

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

---

我們用動(dòng)態(tài)規(guī)劃的思想來解決這個(gè)問題。

確定狀態(tài)表示：根據(jù)經(jīng)驗(yàn)和題目要求，我們用dp[i]表示：以i位置為結(jié)尾的所有子序列中，最長(zhǎng)遞增子序列的長(zhǎng)度。

推導(dǎo)狀態(tài)轉(zhuǎn)移方程：以i位置為結(jié)尾的所有子序列分為2類：長(zhǎng)度為1的子序列，長(zhǎng)度大于1的子序列。如果子序列的長(zhǎng)度是1，那么這個(gè)子序列是遞增子序列。下面我們考慮長(zhǎng)度大于1的子序列。

如果以i位置為結(jié)尾的子序列的長(zhǎng)度大于1，我們可以繼續(xù)細(xì)分為：i位置元素的前面是i - 1位置元素的子序列，i位置元素的前面是i - 2位置元素的子序列，i位置元素的前面是i - 3位置元素的子序列，……，i位置元素的前面是0位置元素的子序列。也就是說，如果子序列中，i位置元素的前面是j位置元素，那么j的范圍是[0, i - 1]。

對(duì)于每一個(gè)j，如果nums[j] < nums[i]，那么這個(gè)子序列就有可能是遞增子序列。要想這個(gè)子序列盡可能得長(zhǎng)，就要找到以j位置為結(jié)尾的最長(zhǎng)遞增子序列，在這個(gè)子序列后面添加nums[i]，即為以i位置為結(jié)尾的最長(zhǎng)遞增子序列。

綜上所述，dp[i]應(yīng)該取：「1」和「所有滿足0 <= j < i并且nums[j] < nums[i]的j中，最大的dp[j]加1」的較大值。

所以，我們可以把dp表的值都初始化為1，其中dp[0] = 1是顯然的。如果i > 0，那么dp[i]就應(yīng)該取：所有滿足0 <= j < i并且nums[j] < nums[i]的j中，最大的dp[j]加1。

填表順序：根據(jù)狀態(tài)轉(zhuǎn)移方程，顯然應(yīng)從左往右填表。

返回值：根據(jù)狀態(tài)表示，應(yīng)返回dp表的最大值。

細(xì)節(jié)問題：dp表的規(guī)模和nums相同，均為1 x n。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();// 創(chuàng)建dp表vector<int> dp(n, 1);// 填表for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}}return *max_element(dp.begin(), dp.end());}
};