面试经典算法题77-最长递增子序列

LeetCode.300

问题描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

思路

1. 状态定义：使用一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。
2. 状态转移方程：对于每个 i，检查在它之前的每个元素 j（即 0 ≤ j < i），如果 nums[i] > nums[j]，则可以将 nums[i] 添加到以 nums[j] 结尾的子序列之后。此时，dp[i] = max(dp[i], dp[j] + 1)。
3. 初始状态：每个元素单独作为子序列时长度为1，因此 dp 数组初始化为 1。
4. 最终结果是 dp 数组中的最大值，即最长严格递增子序列的长度。

参考代码

C++

#include <iostream>
#include <vector>
#include <algorithm> // 为了使用 max 函数

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;

    // 定义 dp 数组，初始长度为 nums 的长度，每个元素初始化为 1
    vector<int> dp(nums.size(), 1);

    // 遍历数组的每个元素
    for (int i = 1; i < nums.size(); ++i) {
        // 遍历当前元素之前的每个元素
        for (int j = 0; j < i; ++j) {
            // 如果当前元素大于之前的元素
            if (nums[i] > nums[j]) {
                // 更新 dp[i]，表示以 nums[i] 结尾的最长递增子序列长度
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // 返回 dp 数组中的最大值，即最长递增子序列的长度
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "输入: [10, 9, 2, 5, 3, 7, 101, 18]" << endl;
    cout << "输出: " << lengthOfLIS(nums1) << endl; // 输出: 4

    vector<int> nums2 = {0, 1, 0, 3, 2, 3};
    cout << "输入: [0, 1, 0, 3, 2, 3]" << endl;
    cout << "输出: " << lengthOfLIS(nums2) << endl; // 输出: 4

    vector<int> nums3 = {7, 7, 7, 7, 7, 7, 7};
    cout << "输入: [7, 7, 7, 7, 7, 7, 7]" << endl;
    cout << "输出: " << lengthOfLIS(nums3) << endl; // 输出: 1

    return 0;
}

Java

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    // 方法：计算最长递增子序列的长度
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        // 初始化 dp 数组，每个位置的初始值为 1
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        // 遍历数组中的每个元素
        for (int i = 1; i < nums.length; i++) {
            // 遍历当前元素之前的每个元素
            for (int j = 0; j < i; j++) {
                // 如果当前元素大于之前的元素
                if (nums[i] > nums[j]) {
                    // 更新 dp[i]，表示以 nums[i] 结尾的最长递增子序列长度
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 返回 dp 数组中的最大值，即最长递增子序列的长度
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("输入: [10, 9, 2, 5, 3, 7, 101, 18]");
        System.out.println("输出: " + lengthOfLIS(nums1)); // 输出: 4

        int[] nums2 = {0, 1, 0, 3, 2, 3};
        System.out.println("输入: [0, 1, 0, 3, 2, 3]");
        System.out.println("输出: " + lengthOfLIS(nums2)); // 输出: 4

        int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
        System.out.println("输入: [7, 7, 7, 7, 7, 7, 7]");
        System.out.println("输出: " + lengthOfLIS(nums3)); // 输出: 1
    }
}

Python

from typing import List

def lengthOfLIS(nums: List[int]) -> int:
    if not nums:
        return 0

    # 初始化 dp 数组，每个位置的初始值为 1
    dp = [1] * len(nums)

    # 遍历数组中的每个元素
    for i in range(1, len(nums)):
        # 遍历当前元素之前的每个元素
        for j in range(i):
            # 如果当前元素大于之前的元素
            if nums[i] > nums[j]:
                # 更新 dp[i]，表示以 nums[i] 结尾的最长递增子序列长度
                dp[i] = max(dp[i], dp[j] + 1)

    # 返回 dp 数组中的最大值，即最长递增子序列的长度
    return max(dp)

if __name__ == "__main__":
    nums1 = [10, 9, 2, 5, 3, 7, 101, 18]
    print("输入: [10, 9, 2, 5, 3, 7, 101, 18]")
    print("输出:", lengthOfLIS(nums1))  # 输出: 4

    nums2 = [0, 1, 0, 3, 2, 3]
    print("输入: [0, 1, 0, 3, 2, 3]")
    print("输出:", lengthOfLIS(nums2))  # 输出: 4

    nums3 = [7, 7, 7, 7, 7, 7, 7]
    print("输入: [7, 7, 7, 7, 7, 7, 7]")
    print("输出:", lengthOfLIS(nums3))  # 输出: 1