1218. Longest Arithmetic Subsequence of Given Difference

yPhantom 2019年10月14日 38次浏览

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

动态规划的几个特征:

  • 多决策求最优解
  • 子问题重复调用,比如 1 + 1 + 1 + 1 + 1 + 1,我们可以直接说出结果等于6。
  • 在一个临时决策中所产生的结果在后续决策中会用到,所以我们用一个数组来存储,这也是我们可以用到递推式的原因

看看知乎上的理解

因此这道题解法如下:

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int maxCount = 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int value: arr) {
            map.put(value, 1 + map.getOrDefault(value - difference, 0));
            maxCount = Math.max(maxCount, map.get(value));
        }
        return maxCount;
    }
}

一开始这道题直接用的暴力遍历的方法,O(n2)的时间复杂度直接TLE了。然后仔细观察题目可以发现,在每次决策过程中(当前这个数在不在最长序列中),都依赖于前一个决策的结果。因此可以用DP。

注意map.getOrDefault方法的使用。