0027.最长增长子序列.md

27.最长增长子序列

题目链接

C++

#include <iostream>
#include <string>
#include <regex>
#include <cstdlib>
#include <vector>
#include <algorithm>
 
 
int LIS(std::vector<int> const &nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);
    for (int end = 1; end < n; ++end) {
        for (int begin = 0; begin < end; ++begin) {
            if (nums[begin] < nums[end]) {
                dp[end] = std::max(dp[end], 1 + dp[begin]);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end());
}
 
std::vector<std::string> split(std::string const &str) {
    std::regex pattern("[\\[\\],]");
    return std::vector<std::string>(
        std::sregex_token_iterator(str.begin(), str.end(), pattern, -1),
        std::sregex_token_iterator()
    );
}
 
int main(int argc, char** argv) {
    std::string line;
    std::getline(std::cin, line);
    std::vector<std::string> str_arr = split(line);
    int n = std::stoi(str_arr[0]);
     
    for (int i = 0; i < n; ++i) {
        std::getline(std::cin, line);
        str_arr = split(line);
        std::vector<int> nums(str_arr.size() - 1);
        std::transform(str_arr.begin() + 1, str_arr.end(), nums.begin(), 
            [](auto &str){ return std::stoi(str); }
        );
        std::cout << LIS(nums) << "\n";
    }
     
    return EXIT_SUCCESS;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        for (int i = 0; i < N; i++) {
            String input = scanner.next();
            int[] nums = parseStringToIntArray(input);
            System.out.println(lengthOfLIS(nums));
        }
    }
    public static int lengthOfLIS (int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
    public static int[] parseStringToIntArray(String input) {
        String[] stringArray = input.replaceAll("[\\[\\]\\s]", "").split(",");
        int[] intArray = new int[stringArray.length];
        for (int i = 0; i < stringArray.length; i++) {
            intArray[i] = Integer.parseInt(stringArray[i]);
        }
        return intArray;
    }
}

方法二：

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < N; i++) {
            String s = sc.nextLine();
            String[] ss = s.replaceAll("[\\[\\]\\s]", "").split(",");
            int[] nums = new int[ss.length];
            for (int j = 0; j < ss.length; j++)
                nums[j] = Integer.parseInt(ss[j]);

            // 贪心
            lengthOfLIS(nums);
            // lengthOfLIS2(nums);

            // 动态规划
            // lengthOfLIS3(nums);
            // lengthOfLIS4(nums);

        }
        sc.close();
    }

    // region 贪心 + 二分查找

    // 一、使用额外空间
    // 时间复杂度: O(nlogn), n为nums的长度
    // 空间复杂度: O(n)
    static void lengthOfLIS(int[] nums) {
        List<Integer> g = new ArrayList<>();
        for (int x : nums) {
            int j = lowerBound(g, x);
            if (j == g.size()) // >= x 的g[j]不存在
                g.add(x);
            else
                g.set(j, x);
        }
        System.out.println(g.size());
    }

    // 二分查找 <= target 的最大下标，若没有，返回g的长度（开区间）
    static int lowerBound(List<Integer> g, int target) {
        int left = -1, right = g.size();
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (g.get(mid) < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    // 二、原地修改
    // 时间复杂度: O(nlogn), n为nums的长度
    // 空间复杂度: O(1)
    static void lengthOfLIS2(int[] nums) {
        int ng = 0; // g 的长度
        for (int x : nums) {
            int j = lowerBound2(nums, ng, x);
            nums[j] = x;
            if (j == ng) // >= x 的g[i]不存在
                ng++;
        }
        System.out.println(ng);
    }

    static int lowerBound2(int[] nums, int right, int target) {
        int left = -1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    // endregion

    // region 动态规划【枚举选哪个】
    // 时间复杂度: O(n^2), n为nums的长度
    // 空间复杂度: O(n)

    // 一、记忆化搜索
    static void lengthOfLIS3(int[] nums) {
        int n = nums.length;
        int[] memo = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dfs(i, nums, memo));
        }
        System.out.println(ans);
    }

    // nums, memo可以提出去，作为全局变量存在
    static int dfs(int i, int[] nums, int[] memo) {
        if (memo[i] > 0)
            return memo[i];

        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                memo[i] = Math.max(memo[i], dfs(j, nums, memo));
            }
        }
        return ++memo[i];
    }

    // 二、递推
    static void lengthOfLIS4(int[] nums) {
        int n = nums.length, ans = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j], dp[i]);
                }
            }
            ans = Math.max(ans, ++dp[i]);
        }
        System.out.println(ans);
    }

    // endregion

}

Python

t = int(input())
 
for _ in range(t):
    # 解析输入
    arr = list(map(int, input().strip()[1:-1].split(',')))
    n = len(arr)
    if n == 0:
        print(0)
        continue
 
    # 初始化动态规划数组
    dp = [1] * n
 
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    # 找到dp中的最大值
    print(max(dp))

方法二：

def length_of_LIS(nums: list) -> None:
    """贪心 + 二分查找"""
    def lowerBound(g: list, target: int) -> int:
        left, right = -1, len(g)
        while left + 1 < right:
            mid = (left + right) // 2
            if g[mid] < target:
                left = mid
            else:
                right = mid
        return right

    g = []
    for x in nums:
        j = lowerBound(g, x)
        if j == len(g):  # >= x的g[j]不存在
            g.append(x)
        else:
            g[j] = x
    print(len(g))


def length_of_LIS_2(nums: list) -> None:
    """贪心 + 二分查找"""
    def lower_bound(nums: list, target: int, left: int, right: int) -> int:
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        return right

    ng = 0
    for x in nums:
        j = lower_bound(nums, x, -1, ng)
        nums[j] = x
        if j == ng:  # >= x的g[j]不存在
            ng += 1
    print(ng)


def length_of_LIS_3(nums: list) -> None:
    """动态规划（dfs）"""
    n = len(nums)

    # dfs(i) 表示以i结尾的最长递增子序列长度
    # @cache # from functools import cache
    def dfs(i: int) -> int:
        res = 0
        for j in range(i):
            if nums[j] < nums[i]:
                res = max(res, dfs(j))
        return res + 1

    ans = 0
    for i in range(n):
        ans = max(ans, dfs(i))
    return ans


def length_of_LIS_4(nums: list) -> None:
    """动态规划（递推）"""
    n = len(nums)
    # dp[i] 表示以i结尾的最长递增子序列长度
    dp = [0] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j])
        dp[i] += 1
    print(max(dp))


if __name__ == "__main__":
    N = int(input())
    for _ in range(N):
        s = input()
        nums = list(
            map(int, s.replace("[", "").replace("]", "").replace(" ", "").split(",")))

        # 贪心
        length_of_LIS(nums)
        # length_of_LIS_2(nums)

        # 动态规划
        # length_of_LIS_3(nums) # 因为无法引入functools.cache，此方法可以在本地跑，kama网上不能跑通，力扣上可以跑通
        # length_of_LIS_4(nums)

Go

package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"

)

func main() {
    var n int
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    n, _ = strconv.Atoi(scanner.Text())
    for i := 0; i < n; i ++ {
        scanner.Scan()
        input := strings.Split(scanner.Text(), ",")
        in_len := len(input)
        firstNum, _ := strconv.Atoi(input[0][1:])
        lastNum, _ := strconv.Atoi(input[in_len-1][:len(input[in_len-1])-1]) 
        in := make([]int, in_len)
        in[0], in[in_len-1] = firstNum, lastNum
        for j := 1; j <= in_len-2; j ++ {
            in[j], _ = strconv.Atoi(input[j])
        }
        fmt.Println(handler(in))
    }
}


func handler(nums []int) int {
    res := 0
    n := len(nums)
    dp := make([]int, n)
    for i := range nums {
        maxLen := 0
        for j := 0 ; j < i; j ++ {
            if nums[j] < nums[i] {
                if dp[j] > maxLen {
                    maxLen = dp[j]
                }
            }
        }
        dp[i] = maxLen+1
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}

Js

C