leetcode 1027：Longest Arithmetic Sequence

本文主要是介绍leetcode 1027：Longest Arithmetic Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode 1027：Longest Arithmetic Sequence

题意：给你一个数组A，求这个数组子序列中中最长等差序列，返回长度。

数组长度是[0,2000]，数值长度是[0,10000]。

思路：简单DP吧。dp[i][j]表示的是以第i个数结尾，差是j的最大长度。

dp[i][A[i] - A[j]] = max(dp[i][A[i] - A[j]],dp[j][A[i]-A[j]]+1);

代码：

class Solution {
public:int longestArithSeqLength(vector<int>& A) {vector<map<int,int>>dp(2002);for (int i = 0; i < A.size(); i++)for (int j = i+1; j < A.size();j++)dp[i][A[j] - A[i]] = 1;int ans = 0;for (int i = 1; i < A.size(); i++){for (int j = 0; j < i; j++){if (dp[j][A[i] - A[j]] != 0){dp[i][A[i] - A[j]] = max(dp[i][A[i] - A[j]],dp[j][A[i]-A[j]]+1);ans = max(ans, dp[i][A[i] - A[j]]);}}}return ans;}
};

 

这篇关于leetcode 1027：Longest Arithmetic Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---