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;
    }
}

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))

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