Ask a google interview question(2)# JobHunting - 待字闺中
B*1
1 楼
Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest possible.
The sequence S1, S2, …, Sk is called an arithmetic progression if
Sj+1 – Sj is a constant
should be DP, but could not figure out the dp function.
Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest possible.
The sequence S1, S2, …, Sk is called an arithmetic progression if
Sj+1 – Sj is a constant
should be DP, but could not figure out the dp function.
