# Problem

Given an array A of integers, return the length of the longest arithmetic subsequence in A.

Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).

# Solution

Use brute force. Traverse the array A and use an assistant matrix “maxlen” to keep the length of every arithmetic subsequence, where maxlen[i][j] represents the length of arithmetic subsequence ended at A[i] with difference of j - 10000 (j - 10000 because the difference can be negative). In addition, a key function to calculate maxlen[i][j] is maxlen[i][A[i] - A[j] + 10000] = maxlen[j][A[i] - A[j] + 10000] + 1.

# Code

``````class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
int **maxlen = new int* [A.size()];
for (int i = 0; i < A.size(); i++)
{
maxlen[i] = new int ;
}
int max = 2;
for (int i = 0; i < A.size(); i++)
{
for (int j = 0; j < 20001; j++)
{
maxlen[i][j] = 1;
}
}
for (int i = 1; i < A.size(); i++)
{
for (int j = 0; j < i; j++)
{
maxlen[i][A[i] - A[j] + 10000] = maxlen[j][A[i] - A[j] + 10000] + 1;
if (max < maxlen[i][A[i] - A[j] + 10000])
{
max = maxlen[i][A[i] - A[j] + 10000];
}
}
}
return max;
}
};
``````

502 Love u

【DP】1027. Longest Arithmetic Sequence

04/30
0
0

ＥＢＮＦ如下，但bfactor不知道怎么推导，选(bool-exp)还是(comparison-exp)? stmt-sequence -> statement { ; statement } statement -> if-stmt | repeat-stmt | assign-stmt | read-stmt......

xiangxw
2010/11/19
332
2

2018/01/03
9
0
【Leetcode】413. Arithmetic Slices

Description A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For examp......

xiagnming
2018/07/31
0
0
[Leetcode] Binary Tree Longest Consecutive Sequence 二叉搜索树最长序列

Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starti......

ethannnli
09/29
0
0

Mysql备份还有这么多套路，还不了解下？

9分钟前
4
0

java后端开发
14分钟前
2
0

demyar
16分钟前
2
0
JDK 12 JVM 垃圾回收器 Shenandoah GC 的实践案例

https://www.infoq.cn/article/L4LU1J0VxXtA6ASeGYbV

perofu
25分钟前
3
0
Linux下的计划任务--cron

linux任务计划cron介绍 大部分系统管理工作都是通过定期自动执行某个脚本来完成的，Linux的cron就是用来定期执行脚本的。 Linux任务计划功能的操作都是通过crontab命令来完成的，常用的选项有...

27分钟前
3
0 