最长等差数列

[knightyui]

题目

给定一个整数数组 A，返回 A 中最长等差子序列的长度。

2 <= A.length <= 2000
0 <= A[i] <= 10000

例子

输入：[3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。

解题思路

创建一个二维的整数数组，长度为A.size()，宽度为20001。
其中array[ x ][ y ], x是A元素的指针位置，y是则两数的差值（差值0是10001，而差值-10000是0），而其值是这条线目前的长度。

这里就好比穿针引线的思路。
当两点间没有线时，连上一条线。接着看到有线时，把这条线延长连到下一个点。

先求出最开始的0号数字和之后数字的差值，然后把长度（也就是2）存入后一个数的号数位置。
比如：A中0号位5，3号位9. 差值是4，就存入array[3][4]=2。
然后以此类推，重复的去弄1号2号3号……

比如[5，1，3，9，7，13，17，12]。
开始分析0号位的5和3号位的9时，得到4的差值，9-5=4,存入array[3][4]=2，
随后分析3号位的9和5号位的13时，找到差值[4]，13-9=4，存入array[5][4]=3，
之后分析5号位的13和6号位的17时，找到差值[4]，17-13=4，存入array[6][4]=4，

类似这样的线很多，最后打印出最大值就好。

代码

    public int longestArithSeqLength(int[] A) {
        int[][] dp = new int[A.length][20001];
	    if (A.length < 2)
	    return 0;

	    int max = 0;
	    for (int i = 1 ; i < A.length; i++) {
	        for (int j = 0; j < i; j++) {
	            int step = A[i] - A[j] + 10000;
	            if (dp[j][step] > 0) {
	                dp[i][step] = Math.max(dp[j][step] + 1, dp[i][step]);
	            } else {
	                dp[i][step] = 2;
	            }
	            max = Math.max(max, dp[i][step]);
	        }
	    }
	return max;
    }