Longest Arithmetic Progression

// Question: Given an array, find longest arithmetic sequence (no need to be consecutive)

Solution 1:
//given a sorted array with no dups
//O(n^2) time, O(n^2) space
   
public class Solution {
   
   public int longestArithmeticProgression(int[] nums) {
		if(nums == null || nums.length < 2) {
			return 0;
		}
		
		//key is diff, value is list of index pair with the same diff
		HashMap<Integer, List<int[]>> map = new HashMap<Integer, List<int[]>>();  
		for(int i=0; i<nums.length-1; i++) {   // 注意这边是i<len-1
			for(int j=i+1; j<nums.length; j++) {
				int diff = nums[j] - nums[i];
				if(!map.containsKey(diff)) map.put(diff, new ArrayList<int[]>());
				map.get(diff).add(new int[]{i, j});
			}
		}
		
		int max = 0;
		for(int diff : map.keySet()) {
			int[] lengths = new int[nums.length];
			Arrays.fill(lengths, 1);    //initialize all nums to 1
			
			for(int[] pair : map.get(diff)) {
				lengths[pair[1]] = lengths[pair[0]] + 1;     //update length of this diff's Arithmetic Progression
				max = Math.max(max, lengths[pair[1]]);
			}
		}
		return max;
	}
}


Solution2: DP
一定要看: http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/
         http://algorithmsandme.in/2014/04/longest-arithmetic-progression/

Given an array of sorted numbers having no duplicates , 
write a program to find the length of the Longest Arithmetic Progression (LLAP等差数列) in it.

Time Complexity: O(n2)
Auxiliary Space: O(n2)

A[i], A[j] and A[k] form an AP if 2* A[j] = A[i] + A[k] where k>j and i<j.

If we formulate a table where Table[i][j] is set to length of AP with first and second element as A[i] and A[j]. 
When j = N, value is set to 2 because every element in array forms an AP of length 2 with last element. 
Move up from N-1 to 0 and fill Table [i][j] bottom up. Search for i < j and k > j such that A[i], A[j] and A[k] form an AP. Then,

Table[i][j] = Table[j][k] + 1
Since we are filling table bottom up and k>j; Table[j][k] would have been already calculated when we are calculating Table[i][j].

代码解释看GeekforGeeks的链接里

public class LongestArithmeticProgression {
	public int lengthOfLongestAP(int[] nums) {
		if(nums == null || nums.length == 0) return 0;
		int n = nums.length;
		if(n <= 2) return n;
		
		int[][] dp = new int[n][n];
		int result = 2; 
		for(int i=0; i<n; i++) {
			dp[i][n-1] = 2;
		}
		for(int j=n-2; j>=1; j--) {
			int i=j-1, k=j+1;
			while(i >= 0 && k <= n-1) {
				if(nums[i] + nums[k] < 2 * nums[j]) {
					k ++;
				} else if(nums[i] + nums[k] > 2 * nums[j]) {
					dp[i][j] = 2;
					i --;
				} else {
					dp[i][j] = dp[j][k] + 1;
					result = Math.max(result, dp[i][j]);
					i--;
					k ++;
				}
			}
			while(i >= 0) {
				dp[i--][j] = 2;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		LongestArithmeticProgression test = new LongestArithmeticProgression();
		int[] nums1 = {1,7,10,13,16,19};
		System.out.println(test.lengthOfLongestAP(nums1));
		int[] nums2 = {1,7,10,15,27,29};
		System.out.println(test.lengthOfLongestAP(nums2));
		int[] nums3 = {2,4,6,8,10};
		System.out.println(test.lengthOfLongestAP(nums3));
	}
}


Question2: Given an array, find longest consecutive arithmetic sequence
// O(n)
public class FindLongestConsecutiveArithmeticProgression {
	public static int findLongestConsecutiveArithmeticSequence(int[] nums) {
		if(nums == null || nums.length == 0) return 0;
		
		// key is diff, value is the start and end index of the arithmetic sequence
		HashMap<Integer, int[]> map = new HashMap<Integer, int[]>();   
		int max = 0;
		for(int i=1; i<nums.length; i++) {
			int diff = nums[i] - nums[i-1];
			if(!map.containsKey(diff)) {
				map.put(diff, new int[]{i-1, i});
			} else {
				int[] pair = map.get(diff);
				if(pair[1] == i-1) {
					map.put(diff, new int[]{pair[0], i});
				} else {
					max = Math.max(max, pair[1]-pair[0]+1);
					map.put(diff, new int[]{i-1, i});
				}
			}
		}
		
		for(int[] pair : map.values()) {
			max = Math.max(max, pair[1]-pair[0]+1);
		}
		return max;
	}
	
	public static void main(String[] args) {
		int[] nums = {1,2,3,8,10,12,14,15,15,16};
		System.out.println(findLongestConsecutiveArithmeticSequence(nums));
	}
}