LeetCode Day 52 Dynamic Programming (13/17)

After practicing stock trading, I started practicing subsequence problems today.

Question 1

300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing

subsequence.(A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.)

With the help of dynamic programming in five parts:

1. Definition of dp[i]
   1. It is important to correctly define the meaning of the dp array in this problem. dp[i] denotes the length of the longest incremental subsequence ending in nums[i] that includes i before i
2. The state transfer equation
   1. The longest ascending subsequence at position i is equal to the maximum of the longest ascending subsequence + 1 at each position j from 0 to i-1. So: if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); Note that instead of comparing dp[i] to dp[j] + 1, we’re taking the maximum value of dp[j] + 1 here.
3. Initialisation of dp[i]
   1. For every i, the corresponding dp[i] (i.e., the longest increasing subsequence) starts with a size of at least 1.
4. Determining the traversal order dp[i] is derived from the longest increasing subsequence at each position from 0 to i-1, so traversing i must be done from front to back.
5. Example of derivation of dp array

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

Question 2

674. Longest Continuous Increasing Subsequence

• Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

  A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

If nums[i] > nums[i - 1], then the length of a continuously increasing subsequence ending in i must be equal to the length of a continuously increasing subsequence ending in i - 1 + 1 .

i.e.: dp[i] = dp[i - 1] + 1.

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1
        dp = [1] * len(nums)
        for i in range(len(nums)-1):
            if nums[i+1] > nums[i]: #连续记录
                dp[i+1] = dp[i] + 1
            result = max(result, dp[i+1])
        return result