LC 300 & LC 674

Solution to LeetCode 300 Longest Increasing Subsequence & LeetCode 674 Longest Continuous Increasing Subsequence

LeetCode 300

Longest Increasing Subsequence (Medium) [link]

Define dp[i] the longest length of the subsequence considering the the part of sequence ended at nums[i]. The recurrence relation is if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j]+1). The base cases are for all i, dp[i]=1.

Time complexity O(n^2). Space complexity O(n).

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

LeetCode 674

Longest Continuous Increasing Subsequence (Easy) [link]

Define dp[i] as the length of increasing subsequence ended with nums[i]. We don’t need to compare any nums[i] and nums[j] (j<i), instead, we need to compare nums[i+1] and nums[i].

class Solution:
    def findLengthOfLCIS(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)):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
            result = max(result, dp[i])
        return result