leetcode热题100.最长递增子序列（动态规划大成）

haloe大家好，今天给大家分享一道动态规划的常考题，经常出现在大厂面试手撕过程中。他就是最长递增子序列🍕祝大家早日oc🍔

Problem: 300. 最长递增子序列

题目

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组 （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路

采用动态规划的思想，定义数组dp[i]为长度为i的子数组的最长子数组的长度，注意其中nums[i]必须被选中，我们发现dp[i]的值是由前面最大的dp[j]+1转移而来。不难得出转移方程：
$dp[i]=max(dp[j])+1,其中0\le j<i且num[j]<num[i]$
最终的答案就是dp数组的最大值

复杂度

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

Code

python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1]*(n+1)
        for i in range(1,n+1):
            for j in range(1,i):
                if nums[j-1]<nums[i-1]:
                    dp[i] = max(dp[j] + 1,dp[i])
        return max(dp)

java

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        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;
    }
}