题目：最长等差数列

• 给定一个整数数组A，返回 A中最长等差子序列的长度。
• 回想一下，A的子序列是列表A[i_1], A[i_2], ..., A[i_k] 其中0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果B[i+1] - B[i](0 <= i < B.length - 1) 的值都相同，那么序列B是等差的。

示例 1：

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

示例 2：

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：

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

来源：力扣（LeetCode）第1027题

链接：https://leetcode-cn.com/problems/longest-arithmetic-sequence

分析：

• 动态规划
• 我们定义两个状态，以i和j为最后两个数时的状态。
• 我们可以穷举所有以i，j结尾时的状态。
• 如果知道后两位数，我们可以计算出前一位数，然后去找一下在前面有没有这个数。如果有，我们就计算i,j为前两个数+1。
• 不过这样需要定义两个状态，还有一种节省空间的做法，只用一个状态，就是以i为结尾时的个数。
• 不过这样会提升时间复杂度，因为有许多重复的计算。
• 我们每次以一个数开头，再把另外的数不停的把符合公差的数加入dp数组。

代码：

• dp(二维)

  class Solution {
  public int longestArithSeqLength(int[] A) {
      int len = A.length;
      int ans = 2;
      int[][] dp = new int[len][len];
      int[] index = new int[10001];// 存下标的数组
      for (int i = 0; i < len - 1; i++) {
          Arrays.fill(dp[i], 2);//一开始至少长度是2。
          for (int j = i + 1; j < len; j++) {
              int pre = 2 * A[i] - A[j];// 算出前一位数
              if (pre < 0 || pre > 10000 || index[pre] == 0) continue;// 尝试去找这个前一位数，如果找不到就不用算下去了。
              dp[i][j] = dp[index[pre]-1][i] + 1;//当前情况下的长度加1，不需要max，因为每一次计算等差数列都是独立计算的。
              ans = Math.max(ans, dp[i][j]);//把每次的最长情况存下来。
          }
          index[A[i]] = i + 1;//因为是子序列，所以还要注意顺序。
      }
      return ans;
  }
  }
  

• dp(一维)

  class Solution {
  int len;
  public int longestArithSeqLength(int[] A) {
      len = A.length;
      int ans = 2;
      int[] dp = new int[len];
      for (int i = 0; i < len; i++) {
          for (int j = i + 1; j < len; j++) {
              int d = A[j] - A[i];
              dp[j] = 2;
              ans = Math.max(ans, dp[j]);
              int next = find(A, A[j] + d, j);
              int pre = j;
              while (next != -1) {
                  dp[next] = dp[pre] + 1;
                  pre = next;
                  next = find(A, A[next] + d, next);
                  if (pre != -1) ans = Math.max(ans, dp[pre]);
              }
          }
      }
      return ans;
  }
  
  public int find(int[] A, int tar, int cur) {
      for (int i = cur + 1; i < len; i++) 
          if (A[i] == tar) return i;
      return -1;
  }
  }