http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/
DP35 最长等差数列 Longest Arithmetic Progression @geeksforgeeks(二)
项数
// Fill entries in last column as 2. There will always be
// two elements in AP with last number of set as second
// element in AP
for(int i=0; i
=1; j--){ int i=j-1, k=j+1; // Search for i and k for j while(i>=0 && k<=n-1){ if(A[i]+A[k] < 2*A[j]){ k++; }else if(A[i]+A[k] > 2*A[j]){ // Before changing i, set L[i][j] as 2 L[i][j] = 2; // 初始化，项数至少为2 i--; }else{ // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side L[i][j] = L[j][k] + 1; // 因为包括了[i,j]和[j,k]两项，比原来的[j,k]多了一项 // Update overall LLAP, if needed llap = Math.max(llap, L[i][j]); // Change i and k to fill more L[i][j] values for current j i--; k++; } } // If the loop was stopped due to k becoming more than // n-1, set the remaining entities in column j as 2 while(i >= 0){ L[i][j] = 2; i--; } } return llap; } }