1027.最长等差数列.cpp

/*
 * @lc app=leetcode.cn id=1027 lang=cpp
 *
 * [1027] 最长等差数列
 *
 * https://leetcode-cn.com/problems/longest-arithmetic-sequence/description/
 *
 * algorithms
 * Medium (41.45%)
 * Likes:    54
 * Dislikes: 0
 * Total Accepted:    6K
 * Total Submissions: 13.4K
 * Testcase Example:  '[3,6,9,12]'
 *
 * 给定一个整数数组 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
 * 
 * 
 */

// @lc code=start
#include <vector>
#include <math.h>
using namespace std;

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int len = A.size();
        if(len < 3)
            return len;
        vector<vector<int>> dp(len, vector<int>(20001, 1));
        int ans = 0;
        for(int i = 1; i < len; ++i){
            for(int j = 0; j < i; ++j){
                int diff = A[i] - A[j] + 10000;
                dp[i][diff] = max(dp[j][diff] + 1, dp[i][diff]);
                if(dp[i][diff] > ans) ans = dp[i][diff];
            }
        }
        return ans;
    }
};
// @lc code=end