算法筆試模拟題精解之“小明的數學作業”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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月份比賽正式開啟！機械鍵盤等你拿！