題目描述
題目鏈接300. 最長遞增子序列
給你一個整數數組?nums?，找到其中最長嚴格遞增子序列的長度。
子序列?是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數組?[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
思路解析
定義一個相同大小的輔助數組，用來記錄到每個元素為止的最長遞增子序列長度
定義一個int類型的ans，用來記錄答案
遍歷數組，在遍歷到每個元素時，對該元素前面的元素進行遍歷，如果前面的元素大，繼續遍歷，如果前面的元素小，則更新該元素并更新答案
代碼實現
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int ans = 1;vector<int>a(nums.size(),1);//定義一個大小為nums.size()的數組for(int i=1;i<nums.size();i++){//遍歷數組for(int j=0;j<i;j++){//遍歷該元素之前的所有元素if(nums[i]<=nums[j])continue;//該元素比之前元素小的話直接跳過a[i]=max(a[i],a[j]+1);//比較該元素當前值與之前元素值加1大小if(a[i]>ans)ans = a[i];//更新答案}}return ans;}
};
)
