Longest Arithmetic Progression

//reference http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

import java.util.*;
public class LongestArithmeticProgression {
	
	/*
	 * warm up
	 * This function returns true if there exist three elements in AP
	 * Assumption: array is sorted
	 * 等差序列性质 a[n - 1] + a[n + 1] = 2a[n]
	 * 我们变量一边数组a[i]设为中间值，a[i - 1] 为第一个， a[i + 1]为第三个
	 * 就变成2sum了，如果和小，增加右边的pointer，和大，减少左边的pointer
	 */
	public static boolean ap3(int[] nums){
		for(int i = 1; i < nums.length - 1; i++){
			int left = i - 1, right = i + 1;
			while(left >= 0 && right < nums.length){
				int sum = nums[left] + nums[right];
				if(sum == 2 * nums[i]) return true;
				else if(sum < 2 * nums[i]) right++;
				else left++;
			}
		}
		return false;
	}
	
	public static int llap(int[] nums){
		if(nums == null){
			return 0;
		}
		if(nums.length <= 2){
			return nums.length;
		}
		int n = nums.length, max = 2;
		//状态为以a[i]. a[j]为前两个元素的等差序列的长度，j > i
		int[][] states = new int[n][n];
		//初始化
		for(int i = 0; i < n; i++){
			states[i][n - 1] = 2;
		}
		for(int j = n - 2; j >= 1; j--){
			int i = j - 1, k = j + 1;
			while(i >= 0 && k < n){
				int sum = nums[i] + nums[k];
				if(sum < 2 * nums[j]) k++;
				else if(sum > 2 * nums[j]){
					states[i][j] = 2;
					i--;
				}else{
					//System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
					states[i][j] = states[j][k] + 1;
					max = Math.max(max, states[i][j]);
					i--;
					k++;
					
				}
			}
			while(i >= 0){
				states[i][j] = 2;
				i--;
			}
		}
		return max;
	}
	
	/*
	 * brute-force O(N^3)
	 */
	public static int llapBF(int[] nums){
		if(nums == null) return 0;
		if(nums.length <= 2) return nums.length;
		int max = 2;
		Arrays.sort(nums);
		/*
		 * a[i], a[j]为等差序列的前两项 N^2 pair
		 * 每一次去找下一个 N
		 * TOTAL O(n^3)
		 */
		int n = nums.length;
		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n; j++){
				int counter = 2;
				int diff = nums[j] - nums[i];
				int target = nums[j] + diff;
				for(int k = j + 1; k < n; k++){
					if(target == nums[k]){
						counter++;
						target = nums[k] + diff;
					}
				}
				max = Math.max(max, counter);
			}
		}
		return max;
	}
	
	public static void main(String[] args){
		int[] nums = {1, 7, 10, 13, 14, 19};
		System.out.println(llapBF(nums));
		int[] nums1 = {2, 4, 6, 8, 10};
		System.out.println(llapBF(nums1));
		int[] nums2 = {1, 7, 10, 15, 27, 29};
		System.out.println(llapBF(nums2));
	}
	
	

}