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;  
   }   

Job Schedule

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum

Naive Thinking:  怎么看怎么像DP，还是经典的那种。
基本逻辑为：
opt[i] // maximum within time [0,i] without overlapping jobs
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[t] + cost of job[k] | where 0<=t<i , job[k]has start time >t, end time<=i)

但是实际做才发现，每次更新opt[i]都要遍历一遍所有job，这很不好，因为即使将job排序也不能有效减少算法复杂度O(n^3)，所以想到了这题跟 maximum non-overlapping intervals 很像。可能可以用Greedy。用Greedy先写一个例子

[  1  ]  [   3     ]
    [    5    ]

如果greedy是优先选start time 小的，这个例子就会通不过。

如果是优先选cost高的，以下这个例子又会不通过。

[  3  ]  [   3     ]
    [    5    ]


那么看来greedy是不可行的，还是老老实写DP。但还是有必要重新讨论一下如何减少一个Loop的。

可不可以先把用什么方法把任意[i,j]时间段对应的job先求出来，如果能在O(n^2)时间内求出来就算是成功的。可以，先将job按start time->end time排序，然后用一个二维数组或者map存每一个时间段对应的job编号，需要用O(n^2)的space。


import java.util.Arrays;
import java.util.Comparator;

class Job{
        int start,end,cost;
        Job(int s, int e, int c){
            start = s;
            end = e;
            cost = c;
        }
    }
public class Solution{

    public static void main(String args[]){
        int n = 1;
        Job[] jobs = new Job[n];
        jobs[0] = new Job(0,3,1);
        jobs[1] = new Job(3,6,3);
        jobs[2] = new Job(1,5,5);
        jobs[3] = new Job(6,7,1);
        jobs[4] = new Job(7,10,4);
        jobs[5] = new Job(6,8,2);
        jobs[6] = new Job(8,10,2);
        jobs[7] = new Job(1,4,6);
        jobs[8] = new Job(3,7,6);
        jobs[9] = new Job(3,8,8);
        Solution s = new Solution();
        System.out.println(s.maxCostOfJobs(jobs));
    }

    public int maxCostOfJobs(Job[] jobs){
        // edge case
        if(jobs.length==0){return 0;}

        // sort the jobs by start time ->end time
        Comparator<Job> comparator = new Comparator<Job>(){
            @Override
            public int compare(Job a, Job b){
                if(a.start > b.start)
                    return 1;
                else if(a.start < b.start)
                    return -1;
                else{
                    if(a.end > b.end)
                        return 1;
                    else if(a.end < b.end)
                        return -1;
                    else
                        return 0;
                }
            }
        };
        Arrays.sort(jobs,comparator);

        // match time interval to job cost
        int min = jobs[0].start, max = jobs[jobs.length-1].end;
        int[][] match = new int[max-min+1][max-min+1];
        Job pre = jobs[0];
        for(int i = 0;i < jobs.length;i++){
            if(jobs[i].start==pre.start && pre.cost > jobs[i].cost){
                match[jobs[i].start-min][jobs[i].end-min] = pre.cost;
            }else{
                match[jobs[i].start-min][jobs[i].end-min] = jobs[i].cost;
                pre = jobs[i];
            }
        }

        // DP to get maximum cost
        int opt[] = new int[max-min+1];
        for(int i = 1;i < opt.length;i++){
            opt[i] = opt[i-1];
            for(int t = 0;t < i;t++)
                opt[i] = Math.max(opt[i], opt[t] + match[t][i]);
        }

        return opt[opt.length-1];

    }
}