Longest Arithmetic Sequenece

There is another question related to Arithmetic Sequence Arithmetic Slice

Given an array, return the number of longest possible arithmetic sequence
For example, [-1, 1, 3, 3, 3, 2, 1, 0}  return 5 because {-1, 0, 1, 2, 3} forms a arithmetic sequence. 

Naive Thinking: 先排序会给找等差序列带来极大的便利。还有就是重复的是差为0的等差数列。
假设从第一个数开始，之后每一个数都会与之形成一个差值，以该差值为步长，看之后的数是否出现在数组中，遍历过的数字对可以放入一个Set中防止重复遍历，并将时间复杂度降低至O(n^2)。

算法复杂度是O(n^2), space O(n^2)

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Map;  
 import java.util.HashMap;  
 import java.util.Set;  
 import java.util.HashSet;  
 import java.util.Arrays;  
 public class Solution{  
   public static void main(String args[]){  
     Solution s = new Solution();  
     int num[] = {1,1,1,3,4,5,6,7,9,11};  
     System.out.println(s.longestArithmeticSeq(num));  
   }  
   // O(n^2)  
   public int longestArithmeticSeq(int num[]){  
     int longest = 0;  
     Map<Integer,Integer> map = new HashMap<Integer, Integer>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     // sort the array  
     Arrays.sort(num);  
     // put num->freq into a map  
     for(int i = 0;i < num.length;i++){  
       if(!map.containsKey(num[i]))  
         map.put(num[i],1);  
       else  
         map.put(num[i],map.get(num[i])+1);  
       longest = Math.max(longest,map.get(num[i]));  
     }  
     // go through the array  
     for(int i = 0;i < num.length-longest+1;i++){  
       for(int j = i+1;j < num.length;j++){  
         int gap = num[j]-num[i];  
         if(gap==0) continue;  
         int cur = num[i];  
         while(map.containsKey(cur+gap)){  
           // use set to record the path  
           List<Integer> list = new ArrayList<Integer>();  
           list.add(cur);  
           cur += gap;  
           list.add(cur);  
           if(set.contains(list)) break;  
           set.add(list);  
         }  
         longest = Math.max(longest, (cur-num[i])/gap+1);  
       }  
       // early break  
       if(longest > num.length/2) break;  
     }  
     return longest;  
   }  
 }   

Improved Way: 上面的方法感觉是比较麻烦而且容易出错，答案是一个DP。想都没想过这道题用DP。
而且这个DP很非常规。在http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/有详细解释。基本逻辑为：
opt[i][j] //  the length of arithmetic sequence by setting num[i] and num[j] as first two elements
// base case
opt[i][j] = 2  for all i and j
// iteration
opt[i][j] = 
if(num[i] + num[k|k>j] = 2*num[j]) opt[j][k]+1

算法复杂度为O(n^2), space O(n^2), 因为定义的是以num[i] 和 num[j] 开头的数列，所以在找的时候要从后往前扫，后面的部分先更新，前面的部分才能囊括后面的信息。

 public int longestArithmeticSeq(int num[]){  
     int longest = 0;  
     int opt[][] = new int[num.length][num.length];  
     Arrays.sort(num);  
     // base case  
     for(int i = 0;i < num.length-1;i++)  
       for(int j = i;j < num.length;j++)  
          opt[i][j] = 2;  
     // iteration  
     for(int j = num.length;j >= 0;j--){  
       int i = j-1, k = j+1;  
       while(i >= 0 && k < num.length){  
         if(num[i] + num[k] < 2*num[j])  
           k++;  
         else if (num[i] + num[k] > 2*num[j])  
           i--;  
         else{  
           opt[i][j] = opt[j][k] + 1;  
           longest = Math.max(longest, opt[i][j]);  
           i--;  
           k++;  
         }  
       }  
     }    
     return longest;  
   }  

还有人在Discuss里提出一个以最大差距为一个参数的DP。基本逻辑为
opt[i][j] // 从num[0..i]的以 j 为步长的等差数列的长度。
// base case
opt[0][j] = 1
// iteration
opt[i][j] = if(num[i]-num[t] == j) opt[t][j] + 1

实际写得时候不用在Iteration部分遍历所有j，因为只需要求出num[i]-num[t]能产生的所有j就行了。

算法复杂度是 O(max(n^2, num[max]-num[min])), space 是 O(n * num[max]-num[min]))。
由于整数最大差值达到2^32，有可能空间不足以创建这个二维数组。所以这个算法有很大的漏洞。但是这个想法是对的。如果空间不足创建二维数组，可以将步长用map来记录，只记录num中可以产生的步长，将步长map到一个list上，list里存所有以该步长为间隔的两个数的集合。这样还是可以使算法复杂度达到O(n^2)， space O(n^2)的。

 public int longestArithmeticSeq(int num[]){  
     if(num.length < 2) return num.length;  
     Arrays.sort(num);  
     int longest = 2;  
     int m = num[num.length-1] - num[0];  
     // opt is defined "the length of longest arithmetix seq in num[0..i] using j as step"  
     int opt[][] = new int[num.length][m+1];  
     // base case  
     for(int i = 0;i <= m;i++) opt[0][i] = 1;  
     // iteration  
     for(int i = 0;i < num.length-1;i++){  
       for(int j = i+1;j < num.length;j++){  
         opt[j][num[j]-num[i]] = opt[i][num[j]-num[i]]+1;  
         longest = Math.max(longest, opt[j][num[j]-num[i]]);  
       }  
     }  
     return longest;  
   }