AlgoPressAppearance
0300-最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence
给你一个整数数组 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
-10^4 <= nums[i] <= 10^4
进阶：
你可以设计时间复杂度为 O(n^2) 的解决方案吗？ 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
思路1 : 模拟0005动态规划【错误】
不符合提议，子序列不是连续的，所以不能用下面的方法处理。
参考代码:有问题
csharp
public class Solution {
public int LengthOfLIS(int[] nums) {
int n = nums.Length;
int[,] dp = new int[n,n];
for(int i=n-1;i>=0;i--){
dp[i,i] = 1; //数组长度
for(int j=i+1;j<n;j++){
//判断两边是否递增
if(nums[i] < nums[i+1] && nums[j] > nums[j-1] ){
dp[i,j] = dp[i+1,j-1] + 2;
}
else{
dp[i,j] = Math.Max(dp[i+1,j],dp[i,j-1]);
}
Console.WriteLine("dp[{0},{1}]={2}",i,j,dp[i,j]);
}
}
return dp[0,n-1];
}
}
思路2，从每个元素遍历【错误】
从第一个元素开始，遇到递增的记录 max 和递增长度
遍历每一个元素，往后重复计算，如果大于 max 则记录 max 的值，最后返回 max
备注： 这个计算方法有问题，如示例[0,1,0,3,2,3] 会返回 3 数组是 [0,1,3] ，但实际可以是4，数组是 [0,1,2,3]
csharp
public class Solution {
public int LengthOfLIS(int[] nums) {
int maxValue;
int curMax;
int maxLength=1;
for(int i=0; i<nums.Length; i++){
maxValue = nums[i];
curMax = 1;
for(int j=i+1;j<nums.Length;j++){
if(nums[j] > maxValue){
curMax++;
maxValue=nums[j];
if(curMax > maxLength){
maxLength = curMax;
}
}
}
}
return maxLength;
}
}
思路3 ：动态规划重新考虑【官方】
dp[i] 表示前面最长严格子序列的长度, 注意nums[i]必须被选取
定义非常重要，dp[i]表示nums[i]必须被选中最长子序列的值
dp[i] = nums[i] > 边界值 ? dp[i-1]+1 : dp[i]
csharp
public class Solution{
public int LengthOfLIS(int[] nums){
int[] dp = new int[nums.Length];
dp[0] = 1;
int maxAns = 1;
for(int i=1; i<nums.Length; i++){
dp[i] = 1;
for(int j=0; j<i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.Max(dp[i],dp[j]+1);
}
}
maxAns = Math.Max(maxAns,dp[i]);
}
return maxAns;
}
}
参考代码 ：复习 2022-04-03
csharp
public class Solution {
public int LengthOfLIS(int[] nums) {
int n = nums.Length;
// 定义动态规划 dp[i] 表示已 i 结尾的递增子序列的最大长度
int[] dp = new int[n];
// 初始化 : 第一个默认长度为 1
dp[0] = 1;
int maxLength = 1;
// 状态转移
for(int i=1; i<n; i++){
//遍历前面所有的数字
int max = 0;
for(int j=0; j<i; j++){
if(nums[i] > nums[j]){
max = Math.Max(dp[j],max);
}
}
dp[i] = max+1;
maxLength = Math.Max(maxLength,dp[i]);
}
return maxLength;
}
}
复习：20220515
csharp
public class Solution {
public int LengthOfLIS(int[] nums) {
int[] dp = new int[nums.Length];
Array.Fill(dp,1);
int max = 1;
for(int i=1; i<nums.Length; i++){
for(int j=0; j<i; j++){
if(nums[i] > nums[j]){ //大于它在进行计算
dp[i] = Math.Max(dp[i],dp[j]+1);
}
}
max = Math.Max(dp[i],max);
//Console.WriteLine("dp[{0}]={1}",i,dp[i]);
}
return max;
}
}