class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
}
};
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 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
O(n log(n)) 吗?原站题解
cpp 解法, 执行用时: 260 ms, 内存消耗: 10.4 MB, 提交时间: 2023-09-27 10:26:40
class Solution {
public:
int lengthOfLIS2(vector<int> &nums) {
int n = nums.size(), memo[n];
memset(memo, 0, sizeof(memo)); // 本题可以初始化成 0，表示没有计算过
function<int(int)> dfs = [&](int i) -> int {
int &res = memo[i];
if (res) return res;
for (int j = 0; j < i; ++j)
if (nums[j] < nums[i])
res = max(res, dfs(j));
return ++res;
};
int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, dfs(i));
return ans;
}
// 递推
int lengthOfLIS(vector<int> &nums) {
int n = nums.size(), f[n];
for (int i = 0; i < n; ++i) {
f[i] = 0;
for (int j = 0; j < i; ++j)
if (nums[j] < nums[i])
f[i] = max(f[i], f[j]);
++f[i];
}
return *max_element(f, f + n);
}
};
golang 解法, 执行用时: 48 ms, 内存消耗: 3.6 MB, 提交时间: 2023-09-27 10:26:09
func lengthOfLIS2(nums []int) (ans int) {
n := len(nums)
memo := make([]int, n) // 本题可以初始化成 0，表示没有计算过
var dfs func(int) int
dfs = func(i int) int {
p := &memo[i]
if *p > 0 {
return *p
}
res := 0
for j, x := range nums[:i] {
if x < nums[i] {
res = max(res, dfs(j))
}
}
res++
*p = res
return res
}
for i := 0; i < n; i++ {
ans = max(ans, dfs(i))
}
return
}
// 递推
func lengthOfLIS(nums []int) (ans int) {
f := make([]int, len(nums))
for i, x := range nums {
for j, y := range nums[:i] {
if y < x {
f[i] = max(f[i], f[j])
}
}
f[i]++
ans = max(ans, f[i])
}
return
}
func max(a, b int) int { if a < b { return b }; return a }
java 解法, 执行用时: 110 ms, 内存消耗: 42.1 MB, 提交时间: 2023-09-27 10:24:56
class Solution {
private int[] nums, memo;
public int lengthOfLIS(int[] nums) {
this.nums = nums;
int n = nums.length;
memo = new int[n]; // 本题可以初始化成 0，表示没有计算过
int ans = 0;
for (int i = 0; i < n; ++i)
ans = Math.max(ans, dfs(i));
return ans;
}
private int dfs(int i) {
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));
return ++memo[i];
}
// 递推
public int lengthOfLIS2(int[] nums) {
int n = nums.length, ans = 0;
int[] f = new int[n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j)
if (nums[j] < nums[i])
f[i] = Math.max(f[i], f[j]);
ans = Math.max(ans, ++f[i]);
}
return ans;
}
}
python3 解法, 执行用时: 2360 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-27 10:24:15
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
f = [0] * len(nums)
for i, x in enumerate(nums):
for j, y in enumerate(nums[:i]):
if x > y:
f[i] = max(f[i], f[j])
f[i] += 1
return max(f)
python3 解法, 执行用时: 2856 ms, 内存消耗: 17.9 MB, 提交时间: 2023-09-27 10:24:02
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
@cache
def dfs(i: int) -> int: # dfs(i) 表示以 nums[i] 结尾的Lis的长度
res = 0
for j in range(i):
if nums[j] < nums[i]:
res = max(res, dfs(j))
return res + 1
return max(dfs(i) for i in range(len(nums)))
python3 解法, 执行用时: 1356 ms, 内存消耗: 13.8 MB, 提交时间: 2020-11-02 15:37:12
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return n
dp = [1 for i in range(n)]
res = dp[0]
for i in range(1, n, 1):
for j in range(0, i, 1):
if nums[j] < nums[i]:
dp[i] = max([dp[j] + 1, dp[i]])
res = max([res, dp[i]])
return res