遇到一个数列问题，求解答。
众所周知，小明是一个数学小能手，有一天数学老师给了小明一个长度为n （2<=n<=5000）的序列，其中第i个数是ai（0<=ai<=1e9）,数学老师想知道这个序列排序后，其中最长的等差子序列的长度是多长，聪明的你能帮小明解决这个问题吗？其中等差子序列的定义为：一个长度为 length 的等差序列 b1、b2……blength，并且序列 b 是序列 a 排序后的子序列。请注意子序列的定义：在原来序列中找出任意数量，任意位置的元素，在不调换这些选出的元素前后顺序的情况下，组成的新序列，称为原序列的子序列。第一行为序列的长度 n（2<=n<=5000），接下来一行是n个数，其中第i个数是ai（0<=ai<=1e9）。输出一行，最长的等差子序列 b 的长度 length。
写回答
-
首先来理解一下题目：数学老师让小明求的是 n 个数中最长的等差数列长度，可以用 dpi 表示以 a[j] 和 a[i] 为结尾的等差序列的最长长度。因为我们肯定要保存一个公差作为状态量，但是直接枚举 0-1e9 又不现实。所以我们巧妙的设计出了这个状态，使得我们的公差就被 a[i]-a[j] 表示了。因此我们的转移就应该是在三个数中转移。即a[i],a[j],a[k]，i 根据等差数列的性质，若 a[i],a[j],a[k] 构成等差序列，那么 a[i]+a[k]=2*a[j]; 每次转移更新答案即可。因此： 输入：6 [0,1,3,5,6,9] 输出：4
2021-12-23 18:40:24赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
