算法笔试模拟题精解之“小明的数学作业”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 129题：小明的数学作业，具体如下：

题目描述

等级：容易

知识点：DP、尺取法

查看题目：小明的数学作业

众所周知，小明是一个数学小能手，有一天数学老师给了小明一个长度为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。

示例1

输入：

6

[0,1,3,5,6,9]

输出：

4

解题思路：

首先来理解一下题目：数学老师让小明求的是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];每次转移更新答案即可。

是不是有思路了呢，点击链接立刻答题：>>

查看题目：129.小明的数学作业 另有在线编程3月份比赛正式开启！机械键盘等你拿！