网站虚拟主机建设,wordpress获取文章简介,如何设计与制作网页,虚拟主机有哪些动态规划
思路#xff1a; 可以参考力扣1218. 最长定差子序列目前不清楚公差#xff0c;可以将序列最大最小值找到#xff0c;公差的范围是 [-(max - min), (max - min)]#xff0c;按公差递增迭代遍历求出最长等差数列#xff1b;
class Solution {
public:int longest…动态规划
思路 可以参考力扣1218. 最长定差子序列目前不清楚公差可以将序列最大最小值找到公差的范围是 [-(max - min), (max - min)]按公差递增迭代遍历求出最长等差数列
class Solution {
public:int longestArithSeqLength(vectorint nums) {auto [minit, maxit] std::minmax_element(nums.begin(), nums.end());int diff *maxit - *minit;int ans 0;for (int d -diff; d diff; d) {std::unordered_mapint, int dp;for (int v : nums) {dp[v] dp[v - d] 1;ans std::max(ans, dp[v]);}}return ans;}
};
时间复杂度比较高应该是哈希表频繁插入导致将 dp 数据结构换成数组数组下标最大值为元素最大值 1
class Solution {
public:int longestArithSeqLength(vectorint nums) {auto [minit, maxit] std::minmax_element(nums.begin(), nums.end());int diff *maxit - *minit;int ans 1;for (int d -diff; d diff; d) {std::vectorint dp(*maxit 1, -1);for (int v : nums) {int prev v - d;// ensure prev is in nums and has exist(or v is the first item)if (prev *minit prev *maxit dp[prev] ! -1) {dp[v] std::max(dp[v], dp[prev] 1);ans std::max(ans, dp[v]);}dp[v] std::max(dp[v], 1);}}return ans;}
};
——————————————————————————————
