← 返回目录

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

第 33 / 74 卷日期：

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

贡献者 | 猿圈

简介：关键在于对题目的了解，数学老师让小明求的是 n 个数中最长的等差数列

长度，可以用 dp[i][j] 表示以 a[j] 和 a[i] 为结尾的等差序列的最长长度。

题目描述

等级：容易

知识点：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]; 每次转移更新答案即可。

是不是有思路了呢，点击链接立刻答题：>> 查看题目：小明的数学作业

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”