動態規劃法求最長遞增子序列，?題目鏈接：力扣

思路：

一、遍歷數組，維護遞增子序列的最大值

代碼：

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {
if(nums.size()==1)
return 1;
int l=1;
int max_length=1;
for(int i=0;i<nums.size()-1;i++)
{if(nums[i]<nums[i+1]){ l++;max_length=max(max_length,l);}else {l=1;}
}
return max_length;}
};

?二.動態規劃

定義dp數組：? ? ? ? dp[i]表示以nums[i]結尾最長遞增子序列

狀態轉移方程：? ? dp[i]=dp[i-1]?+1,如果nums[i]>nums[i-1]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?dp[i]=1,??如果 nums[i] <nums[i-1]

出口：? ? ? ? ? ? ? ? ??dp[0]=1

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {
if(nums.size()==1)
return 1;
vector<int>dp(nums.size());
dp[0]=1;
int max_length=0;
for(int i=1;i<nums.size();i++)
{if(nums[i]>nums[i-1]){dp[i]=dp[i-1]+1;max_length=max(max_length,dp[i]);}else{dp[i]=1;max_length=max(max_length,dp[i]);}
}
return max_length;}
};