lintcode 46

https://www.lintcode.com/contest/46/

1488. 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层循环+Set，Python TLE，Java MLE（我艹）
优化成Set数组形式，还是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数组减小计算量了

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;
        
        // 外层循环第二个数
        for(int j=a.length-2;j>=1;j--) {
            int i=j-1, k=j+1;
            // 内层循环第一个数，用i,k 2个循环变量
            while(i>=0 && k<=a.length-1) {
                if(a[i]+a[k]<2*a[j]) {
                    // dp[i][j]可能还有更优值，所以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跳出的循环，还需要求出剩下的i
            while(i>=0) {
                dp[i][j]=2;
                i--;
            }
        }
        
        return max;
    }
}

许久没刷题了，感觉校招要崩，一直在用Python，刷题老是TLE，FUCK