给定一个长度为 n 的数组a,求它的最长严格上升子序列的长度。 所谓子序列,指一个数组删掉一些数(也可以不删)之后,形成的新数组。例如 [1,5,3,7,3] 数组,其子序列有:[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。 我们定义一个序列是 严格上升 的,当且仅当该序列不存在两个下标 和 满足 且 。 数据范围: , 要求:时间复杂度 , 空间复杂度
示例1
输入
[1,4,7,5,6]
输出
4
说明
最长上升子序列为 [1,4,5,6] ,长度为4。
加载中...
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] a) { // write code here } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型vector 给定的数组 * @return int整型 */ int LIS(vector
& a) { // write code here } };
#coding:utf-8 # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 该数组最长严格上升子序列的长度 # @param a int整型一维数组 给定的数组 # @return int整型 # class Solution: def LIS(self , a ): # write code here
using System; using System.Collections.Generic; class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ public int LIS (List
a) { // write code here } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ function LIS( a ) { // write code here } module.exports = { LIS : LIS };
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 该数组最长严格上升子序列的长度 # @param a int整型一维数组 给定的数组 # @return int整型 # class Solution: def LIS(self , a: List[int]) -> int: # write code here
package main import "fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ func LIS( a []int ) int { // write code here }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @param aLen int a数组长度 * @return int整型 */ int LIS(int* a, int aLen ) { // write code here }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 该数组最长严格上升子序列的长度 # @param a int整型一维数组 给定的数组 # @return int整型 # class Solution def LIS(a) # write code here end end
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ def LIS(a: Array[Int]): Int = { // write code here } }
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ fun LIS(a: IntArray): Int { // write code here } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] a) { // write code here } }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ export function LIS(a: number[]): number { // write code here }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ func LIS ( _ a: [Int]) -> Int { // write code here } }
struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 该数组最长严格上升子序列的长度 * @param a int整型一维数组 给定的数组 * @return int整型 */ pub fn LIS(&self, a: Vec
) -> i32 { // write code here } }
[1,4,7,5,6]
4