递增序列主题Code

找到一个整数数组中的最长递增子序列的长度

def dp_inc(nums):  
    # 如果输入的数组为空，则返回一个长度为0的递增子序列，因此返回0  
    if not nums:  
        return 0  
    # 获取数组的长度  
    length = len(nums)  
    # 初始化一个长度与输入数组相同的数组，用于存储以当前元素结尾的最长递增子序列的长度，初始值都为1  
    dp = [1] * length  
    # 遍历数组中的每个元素  
    for i in range(1, length):  
        # 遍历当前元素之前的所有元素  
        for j in range(i):  
            # 如果找到一个比当前元素小的元素，那么可以尝试将当前元素添加到以该小元素结尾的递增子序列中  
            if nums[i] > nums[j]:  
                # 更新以当前元素结尾的最长递增子序列的长度  
                dp[i] = max(dp[i], dp[j] + 1)  
    # 返回最长递增子序列的长度  
    return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

找出整数数组中的最长连续递增子序列的长度

def conti_inc(nums):  
    # 如果输入的数组为空，则返回一个长度为0的连续递增子序列，因此返回0  
    if not nums:  
        return 0  
    # 获取数组的长度  
    length = len(nums)  
    # cur_len用于存储当前连续递增子序列的长度，初始值为1  
    cur_len = 1  
    # max_len用于存储最长连续递增子序列的长度，初始值为1  
    max_len = 1  
    # 遍历数组中的每个元素，注意这里用到length-1，因为不需要检查最后一个元素之后的元素  
    for i in range(0, length-1):  
        # 如果下一个元素大于当前元素，那么当前连续递增子序列长度加1  
        if nums[i + 1] > nums[i]:  
            cur_len += 1  
        # 如果下一个元素不大于当前元素，那么当前连续递增子序列中断  
        # 需要比较当前连续递增子序列长度和最长连续递增子序列长度，并更新最长长度  
        # 然后将当前连续递增子序列长度重置为1  
        else:  
            max_len = max(cur_len, max_len)  
            cur_len = 1  
    # 最后需要再比较一次当前连续递增子序列长度和最长连续递增子序列长度，以防最长长度在最后一段  
    return max(cur_len, max_len)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

找到矩阵中的最长递增路径

# 定义一个函数，用于找到矩阵中的最长递增路径  
def longestIncreasingPath(matrix):  
    # 如果矩阵为空，返回0  
    if not matrix:  
        return 0  
  
    # 获取矩阵的行数和列数  
    m, n = len(matrix), len(matrix[0])  
    # 初始化一个二维数组，用于存储以每个元素为结尾的最长递增路径的长度，初始值都为1  
    dp = [[1] * n for _ in range(m)]    
  
    # 定义一个深度优先搜索的函数  
    def dfs(i, j):  
        # 如果dp[i][j]大于1，直接返回dp[i][j]，避免重复计算  
        if dp[i][j] > 1:  
            return dp[i][j]  
  
        # 定义四个方向：右、下、左、上  
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]    
        for dx, dy in directions:  
            # 计算新的坐标位置  
            x, y = i + dx, j + dy  
            # 如果新的坐标位置在矩阵内，并且该位置的值大于当前位置的值  
            if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:  
                # 更新以当前位置为结尾的最长递增路径的长度  
                dp[i][j] = max(dp[i][j], dfs(x, y) + 1)  
  
        # 返回以当前位置为结尾的最长递增路径的长度  
        return dp[i][j]  
  
    # 初始化最长路径的长度为0  
    max_len = 0  
    # 遍历矩阵中的每个元素  
    for i in range(m):  
        for j in range(n):  
            # 更新最长路径的长度  
            max_len = max(max_len, dfs(i, j))  
  
    # 返回最长路径的长度  
    return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40