题目
分析
简单的逻辑分析问题,因为是等差序列,所以只需要遍历数组,然后每次以当前位置为结尾的位置,然后再加上之前的所有值即可,同时动态维护最大值,就能得到答案.
代码
C++
class Solution { public: int longestSubsequence(vector& arr, int d) { int res = 0; // 记录下当前位置之前的所有情况 unordered_map m; for(int x : arr) { // 以当前位置为结尾,所以+1,然后计算和前面可以安排的序列长度 m[x] = 1 + m[x - d]; // 动态维护最大值 res = max(res, m[x]); } return res; } };
java
class Solution { public int longestSubsequence(int[] arr, int difference) { int ans = 0; Mapdp = new HashMap (); for (int v : arr) { dp.put(v, dp.getOrDefault(v - difference, 0) + 1); ans = Math.max(ans, dp.get(v)); } return ans; } } 作者:LeetCode-Solution
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)