Introduction
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference。
子序列是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从arr 派生出来的序列。
Input
第一行给出数组arr的元素个数，第二行给出arr中各个元素的值，第三行给出等差difference。其中，1 <= arr.length <=105,−104<= arr[i], difference <=10^4
Output
对每一组输入，在一行中输出最长等差子序列的长度。
Sample
input
5 1 2 3 4 5 1
output
5
Solution
import java.util.HashMap; import java.util.Scanner; public class Main5 { public static void main(String[] args) { Scanner s=new Scanner(System.in); int n=s.nextInt(); int[] arr=new int[n]; for(int i=0;i<n;i++){ arr[i]=s.nextInt(); } int k=s.nextInt(); int ans=0; HashMap<Integer,Integer> map=new HashMap(); for(int i=0;i<n;i++){ int num=map.getOrDefault(arr[i]-k,0); map.put(arr[i],num+1); ans=Math.max(num+1,ans); } System.out.println(ans); } }
Experience
动态规划可以分为数组或者Map实现，当需要构造数组的长度很大的时候，推荐就使用Map了
