300. Longest Increasing Subsequence

#Given you an integer array nums, find the length of the longest strictly increasing subsequence in it.
# Subsequence is a sequence derived from an array, deleting (or not deleting) elements in the array without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
#
# Example 1:
# Input: nums = [10,9,2,5,3,7,101,18]
# output: 4
 # Explanation: The longest increasing subsequence is [2,3,7,101], so the length is 4.
#
# Example 2:
# Input: nums = [0,1,0,3,2,3]
# output: 4
#
# Example 3:
# Input: nums = [7,7,7,7,7,7,7]
# output: 1

1. The definition of dp[i]
dp[i] indicates the length of the longest increasing subsequence ending with nums[i] including i before i

2. State transition equation
 There are two layers of for loops here, one loop itself, and then within the loop, compare itself with the previous one, if it is larger, then add 1 to the previous number
if nums[i] > nums[j]:dp[i] = max(dp[i],dp[j]+1)

3. Initialization of dp[i]
There is at least one number, so it can be assigned all 1
dp = [1 for _ in range(len(nums)) ]

4. Traverse shunxu
 dp[i] is derived from the longest increasing subsequence with positions from 0 to i-1, then traversing i must be traversed from front to back.
j actually traverses from 0 to i-1, so it doesn't matter whether it is traversed from front to back or from back to front, as long as the elements from 0 to i-1 are traversed.  So it traverses forward and backward by default.

5. Derivation
 The dp is as follows:
Take nums = [10,9,2,5,3,7,101,18] as an example
i = 0 dp = [1,1,1,1,1,1,1,1]

i = 1 dp = [1,1,1,1,1,1,1,1] # Because num[1] = 9 does not satisfy the number greater than the number before the subscript is [1], so the number array remains unchanged
 i = 2 dp = [1,1,1,1,1,1,1,1] # Because nums[2] = 2, not greater than the previous 10 and 9, so the array remains unchanged
 i = 3 dp = [1,1,1,2,1,1,1,1] # Because nums[3] = 5, only greater than 2, so add 1 on the basis of 2
 i = 4 dp = [1,1,1,2,2,1,1,1] # Because nums[4] = 3, only greater than 2, so add 1 on the basis of 2
 i = 5 dp = [1,1,1,2,2,3,1,1] # Because nums[5] = 7, which is greater than 2, 5, 3, add 1 to each of these three numbers , and then take the maximum value, which is the longest sequence at this time
 i = 6 dp = [1,1,1,2,2,3,4,1] # Because nums[6] = 101, greater than 2, 5, 3, 7, so take the corresponding subscript value 2, 5 , After adding 1 to the value of 3, 7, take the maximum value, that is, max(3,3,4)
i = 7 dp = [1,1,1,2,2,3,4,4] # Because nums[7] = 18, the situation is the same as above

class Solution:
    def lengthOfLIS(self, nums: [int]) -> int:
        if len(nums) == 1:
            return 1
        dp = [1 for _ in range(len(nums)) ]
        # res = 0
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
            # res = max(res, dp[i])  # take the long subsequence
            # It turned out to be return res, which is the same as mine.
        return max(dp)


if __name__ == '__main__':
    nums = [0, 1, 0, 3, 2, 3]
    nums = [7, 7, 7, 7, 7, 7, 7]
    nums = [7]
    tmp = Solution()
    res = tmp.lengthOfLIS(nums)
    print(res)

674. Longest Continuous Increasing Sequence

#Given an unsorted integer array, find the longest and continuously increasing subsequence, and return the length of the sequence.
# Continuously increasing subsequences can be determined by two subscripts l and r (l < r), if for each l <= i < r, there are nums[i] < nums[i + 1], then the subsequence
 # The sequence [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] is a continuously increasing subsequence.
#
# Example 1:
# Input: nums = [1,3,5,4,7]
# output: 3
 # Explanation: The longest continuous increasing sequence is [1,3,5], with a length of 3.
# Although [1,3,5,7] is also an ascending subsequence, it is not continuous because 5 and 7 are separated by 4 in the original array.
#
# Example 2:
# Input: nums = [2,2,2,2,2]
# output: 1
 # Explanation: The longest continuous increasing sequence is [2], with a length of 1.
#
# 1 <= nums.length <= 104
# -109 <= nums[i] <= 109

1. Determine the meaning of the dp array (dp table) and the subscript
 dp[i]: The length of the continuously increasing subsequence ending with subscript i is dp[i].

2. Determine the recursive formula
 If nums[i] > nums[i - 1], then the length of the continuously increasing subsequence ending with i must be equal to the length of the continuously increasing subsequence ending with i - 1 + 1
 That is: dp[i] = dp[i - 1] + 1;

3. How to initialize the dp array
 The length of the continuously increasing subsequence ending with the subscript i should be at least 1, that is, the element nums[i].
dp = [1] * size

4. Determine the traversal order
 Traverse from front to back, loop once

5. Example derivation dp array
 Take nums = [1, 3, 5, 4, 7] as an example
 The array state is:
i = 0, dp = [1,1,1,1,1]
i = 1, dp = [1,2,1,1,1]
i = 2, dp = [1,2,3,1,1]
i = 3, dp = [1,2,3,1,1]
i = 4, dp = [1,2,3,1,2]

class Solution:
    def findLengthOfLCIS(self, nums: [int]) -> int:
        size = len(nums)
        dp = [1] * size
        for i in range(1,size):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
        return max(dp)

    # The Greedy Solution of Caprice
    def findLengthOfLCIS1(self, nums: [int]) -> int:
        result = 1 #Consecutive subsequences are at least 1
        count = 1
        for i in range(len(nums)-1):
            if nums[i+1] > nums[i]: #continuous recording
                count += 1
            else: #Discontinuous, count starts from the beginning
                count = 1
            result = max(result, count)
        return result

    def findLengthOfLCIS2(self, nums: [int]) -> int:
        # It’s useless to use dynamic programming, and it’s forced to call out by yourself. Here, a value smaller than the last value is added to the array, so that the program can enter the else, and avoid because
        # The last value is the largest, causing the value of res not to be updated
        size = len(nums)
        res = 1
        if size == 1:
            return res
        last = nums[-1]
        nums.append(last-1)
        size += 1
        for i in range(size):
            tmp = 1
            for j in range(i+1,size):
                if nums[j] > nums[j-1]:
                    tmp += 1
                else:
                    res = max(tmp,res)
                    break
        return res
if __name__ == '__main__':
    nums = [1, 3, 5, 4, 7]
    nums = [2, 2, 2, 2, 2]
    nums = [1, 3, 5, 7]
    nums = [1,3,5,4,2,3,4,5]
    tmp = Solution()
    res = tmp.findLengthOfLCIS(nums)
    print(res)

718. Longest Repeating Subarray

# Given two integer arrays nums1 and nums2, return the length of the common and longest subarray in the two arrays.
#
# Example 1:
# Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
# output: 3
 # Explanation: The longest common subarray is [3,2,1].
#
# Example 2:
# Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
# output: 5
#
# hint:
# 1 <= nums1.length, nums2.length <= 1000
# 0 <= nums1[i], nums2[i] <= 100

1. Determine the meaning of the dp array and subscript
 dp[i][j] : A that ends with subscript i - 1, and B that ends with subscript j - 1, and the length of the longest repeated subarray is dp[i][j].
(Special attention: "A that ends with i - 1" indicates that it must be a string ending with A[i-1] )

2. Determine the recursive formula
 According to the definition of dp[i][j], the state of dp[i][j] can only be derived from dp[i - 1][j - 1], traversing i and j starts from 1
dp[i][j] = dp[i - 1][j - 1] + 1;

3. How to initialize
 According to the definition of dp[i][j], dp[i][0] and dp[0][j] are actually meaningless
 In order to facilitate the recursive formula, dp[i][0] and dp[0][j] are initialized to 0

4. Determine the traversal order
 It will be all right

5. Example derivation dp array
A: [1,2,3,2,1]，B: [3,2,1,4]
   B: 3, 2, 1, 4
 A 0 0 0 0 0 # Initialized 0
 1 0 0 0 1 0 # The numbers are consistent, see the value of [i-1][j-1] plus 1,
2 0 0 1 0 0 # Same as above, the number 2 here is the same, but it was not equal before
3  0  1  0  0  0
 2 0 0 2 0 0 # Here it is traversed until 2 is equal, and at the same time push forward, the previous 3 is also equal, add 1 on the previous basis
 1 0 0 0 3 0 # ditto

class Solution:
    def findLength(self, nums1:[int], nums2:[int]) -> int:
        dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]
        result = 0
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                result = max(result, dp[i][j])
        return result

    def findLength2(self, nums1:[int], nums2:[int]) -> int:
        # The creation of a two-dimensional array is associated with the order of traversal. Although anyone can traverse first, it must be consistent with the array
        # Pay attention to the creation of dp, the order of the two for loops is compared with if
        dp = [[0] * (len(nums1)+1) for _ in range(len(nums2)+1)]
        result = 0
        for i in range(1, len(nums2)+1):
            for j in range(1, len(nums1)+1):
                if nums2[i-1] == nums1[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                result = max(result, dp[i][j])
        return result


if __name__ == '__main__':
    nums1 = [1,2,3,2,1]
    # nums1 = [0,0,0,0,0]
    nums2 = [3,2,1,4,7]
    nums2 = [3,2,1,4]
    # nums2 = [0,0,0,0,0]
    tmp = Solution()
    res = tmp.findLength(nums1,nums2)
    print(res)