题解 | 最长上升子序列(一)

1、解题思路

1. 动态规划：定义 dp[i] 为以 arr[i] 结尾的最长严格上升子序列的长度。初始条件：每个 dp[i] 初始化为 1（因为每个元素本身就是一个长度为 1 的子序列）。状态转移方程： 对于每个 i，遍历所有 j < i，如果 arr[j] < arr[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
2. 优化：使用一个数组 dp 来存储中间结果，空间复杂度为 O(n)。遍历数组时，对每个元素 arr[i]，检查之前的所有元素 arr[j]（j < i）并更新 dp[i]。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        if (arr.empty()) {
            return 0;
        }

        int n = arr.size();
        vector<int> dp(n, 1);
        int max_len = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[j] < arr[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_len = max(max_len, dp[i]);
        }

        return max_len;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        if (arr.length == 0) return 0;
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max_len = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max_len = Math.max(max_len, dp[i]);
        }
        return max_len;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定数组的最长严格上升子序列的长度。
# @param arr int整型一维数组 给定的数组
# @return int整型
#
class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        if not arr:
            return 0
        n = len(arr)
        dp = [1] * n
        max_len = 1
        for i in range(1, n):
            for j in range(i):
                if arr[j] < arr[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
            max_len = max(max_len, dp[i])
        return max_len

3、复杂度分析

• 时间复杂度：O(n²)，其中 n 是数组的长度。每个元素需要与之前的所有元素进行比较。
• 空间复杂度：O(n)，用于存储 dp 数组。