leetcode 最长递增子序列 中等 - rookie_Acmer - D1h.Net第一号博客
返回主页

Wh1t3zZ

leetcode 最长递增子序列 中等

 

 

① dp:dp[i] 表示以 i 结尾的最长上升子序列长度,if(dp[j] < dp[i + 1]) dp[i] = max(dp[i], dp[j + 1]),其中 0 <= j < i.

② 贪心 + 二分:看代码比较合适

// dp class Solution { public: int lengthOfLIS(const vector<int>& nums) { vector<int> dp(nums.size(), 1); for(int i = 0; i < nums.size(); ++ i) { for(int j = 0; j < i; ++ j) { if(nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } } int ret = 0; for(int &len : dp) ret = max(ret, len); return ret; } };
// 贪心 + 二分 class Solution { public: int lengthOfLIS(const vector<int>& nums) { vector<int> tmpLis; for(int i = 0; i < nums.size(); ++ i) { if(tmpLis.empty() || tmpLis.back() < nums[i]) { tmpLis.push_back(nums[i]); } else { auto ptr = lower_bound(tmpLis.begin(), tmpLis.end(), nums[i]); *ptr = nums[i]; } } return (int)tmpLis.size(); } };

 

posted @ 2021-09-16 23:54  rookie_Acmer  阅读(3)  评论(0编辑  收藏  举报
Copyright © 2021 rookie_Acmer
Powered by .NET 6 on Kubernetes

问答 28u iTmz.Net 3q科技 A8团队1 A8团队2 A8团队3 A8备