Longest Arithmetic Sequence [LeetCode 1027]

https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/

N要素の配列Aがある。
ここから、等差数列である連続でなくてもよい部分列を取り出すときの、長さの最大値を求めよ。

N≦2000, A[i]≦10000
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　

前提知識

• 動的計画法

解説

https://leetcode.com/contest/weekly-contest-132/submissions/detail/222250366/

DPで解く。
dp[a][b] := 等差数列で末尾2つがA[a],A[b]であるような部分列の最大長
これを計算していこう。
テクを使おう。
　
【テク17】遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる
　
dp[a][b]からの遷移は、公差がd=A[b]-A[a]であるため、次はA[b]+dであるような要素をとってくればいいが、最大長にするためには貪欲にbに一番近い遷移だけを採用すればいい。
これで各状態について遷移が1つになるので、O(N^2)で間に合う。
　
A[b]+dであるようなbに一番近い添字の取得は、
E[x] := A[i]=xであるようなiの配列（ソート済み）
を作っておき、upper_boundでとってくればいい。
全体でO(N^2logA_MAX)で間に合う。

int dp[2020][2020];
vector<int> E[30101];
#define base 10000
class Solution {
public:
	int longestArithSeqLength(vector<int>& A) {
		int N = A.size();
		rep(i, 0, N) E[A[i] + base].push_back(i);
		rep(i, 0, 30101) sort(all(E[i]));

		rep(i, 0, N) rep(j, 0, N) dp[i][j] = 2;

		rep(a, 0, N) rep(b, a + 1, N) {
			int d = A[b] - A[a];
			int nxt = A[b] + d + base;

			int id = upper_bound(all(E[nxt]), b) - E[nxt].begin();
			if (id < E[nxt].size()) {
				int c = E[nxt][id];
				chmax(dp[b][c], dp[a][b] + 1);
			}
		}

		rep(i, 0, 30101) E[i].clear();

		int ans = 0;
		rep(i, 0, N) rep(j, 0, N) chmax(ans, dp[i][j]);
		return ans;
	}
};