最长递增子序列（LCS）

[编程题]最长递增子序列（LCS）

热度指数：2413 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定一个序列 An = a1 ,a2 , ... , an ，找出最长的子序列使得对所有 i < j ，ai < aj 。求出这个子序列的长度

输入描述:

输入的序列

输出描述:

最长递增子序列的长度

示例1

输入

1 -1 2 -2 3 -3 4

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    arr:=[]int{}
    var x int
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        arr=append(arr,x)
    }
    dp:=make([]int,len(arr))
    max:=0
    for i,x:=range arr{
        dp[i]=1
        for j:=0;j<i;j++{
            if arr[j]<x&&dp[j]+1>dp[i]{
                dp[i]=dp[j]+1
            }
        }
        if dp[i]>max{
            max=dp[i]
        }
    }
    fmt.Print(max)
}

发表于 2023-03-20 21:42:32 回复(0)