Given an integer array arr
and an integer difference
, return the length of the longest subsequence in arr
which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference
.
Example 1:
Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element.
Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1].
Constraints:
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
Solution: DP
dp[i] := max length of sequence ends with x
dp[x] = max(0, dp[x – diff]) + 1
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: int longestSubsequence(vector<int>& arr, int d) { unordered_map<int, int> dp; int ans = 0; for (int x : arr) ans = max(ans, dp[x] = dp[x - d] + 1); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment