Leetcode 300. 最长递增子序列(一维数组dp)

比眉伴天荒 2022-10-13 12:42 127阅读 0赞

#### 题目重述 ####

给你一个整数数组 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

*  转移方程：dp\[i\] = max(dp\[j\])+1,其中0≤j<i且num\[j\]<num\[i\]
 *  dp\[i\]表示以nums\[i\]作为结尾的递增子序列最大长度

#### Java实现 ####

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            // 转移方程：dp[i] = max(dp[j])+1,其中0≤j<i且num[j]<num[i]
            // dp[i]表示以nums[i]作为结尾的递增子序列最大长度
            int[] dp= new int[nums.length];
            dp[0] = 1;
            int maxVal = 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);
                    }
                }
                if(dp[i]>maxVal)
                {
        
                    maxVal = dp[i];
                }
            }
            return maxVal;
    
        }
    }