https://www.lintcode.com/contest/46/
- Longest Sequence
Description
Given an array a containing n positive integers, you can arbitrarily select a number of numbers to form an arithmetic progression, what is the maximum length of the arithmetic progression that can be composed?
The length of the array does not exceed 5000
Guarantee that a[i]a[i] is different from each other
a[i] <= 1e9a[i]<=1e9
Have you met this question in a real interview?
Example
Given a = [1,2,5,9,10],贷屎，return 3.
Explanation:
You can select [1, 5, 9] to form an arithmetic progression. The length of this is the longest, which is 3
Given a = [1,3]裳擎，return 2.
Explanation:
At this time, only the series [1, 3] can be selected to form an arithmetic progression with the length of 2
2層循環(huán)+Set讨彼，Python TLE，Java MLE（我艸）
優(yōu)化成Set數(shù)組形式帝璧，還是Python TLE，Java MLE（我艸）
https://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/望迎，居然這么tricky席爽，服了
dp[i][j]表示前面2位為a[i],a[j]的最長AP，然后從后往前計算就可以利用dp數(shù)組減小計算量了
package lint5;
import java.util.Arrays;
public class Solution {
public int getAnswer(int[] a) {
// Write your code here
if(a.length==0 || a.length==1) return a.length;
int max=2;
Arrays.sort(a);
// dp[i][j]表示前面2位為a[i],a[j]的最長AP
int[][]dp=new int[a.length][a.length];
for(int i=0;i<a.length;i++) dp[i][a.length-1]=2;
// 外層循環(huán)第二個數(shù)
for(int j=a.length-2;j>=1;j--) {
int i=j-1, k=j+1;
// 內(nèi)層循環(huán)第一個數(shù)蹦玫，用i,k 2個循環(huán)變量
while(i>=0 && k<=a.length-1) {
if(a[i]+a[k]<2*a[j]) {
// dp[i][j]可能還有更優(yōu)值赎婚，所以i不減
k++;
} else if (a[i]+a[k]>2*a[j]) {
dp[i][j] = 2;
i--;
} else {
dp[i][j] = dp[j][k]+1;
max = Math.max(max, dp[i][j]);
i--;
k++;
}
}
// 可能是由于k跳出的循環(huán)，還需要求出剩下的i
while(i>=0) {
dp[i][j]=2;
i--;
}
}
return max;
}
}
許久沒刷題了樱溉，感覺校招要崩惑淳，一直在用Python，刷題老是TLE饺窿，F(xiàn)UCK
