Longest Arithmetic Subsequence 最长等差序列

例子，1、3、9、5、7。 输出四。因为1、3、5、7。

http://www.1point3acres.com/bbs/thread-229482-1-1.html

Solution 1: HashMap O(n^2); O(n^2)

    public int maxLenArithmeticSeq(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer>[] map = new HashMap[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            map[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                int count1 = map[i].getOrDefault(diff, 1);
                int count2 = map[j].getOrDefault(diff, 1);
                int len = Math.max(count2 + 1, count1);
                max = Math.max(max, len);
                map[i].put(diff, len);
            }
        }
        return max;
    }

Solution 2: HashMap + DP O(n^2); O(n^2)

    private int longestArithmeticProgression(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Map<Integer, List<List<Integer>>> map = new HashMap<>();//key is diff, value is pair of indices
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int diff = nums[j] - nums[i];
                if (!map.containsKey(diff)) {
                    map.put(diff, new ArrayList<>());
                }
                List<Integer> pair = new ArrayList<>(Arrays.asList(i, j));
                map.get(diff).add(pair);
            }
        }

        int max = 0;
        for (int key : map.keySet()) {
            int[] lengths = new int[nums.length];
            for (int i = 0; i < lengths.length; i++) {
                lengths[i] = 1;//initialize all nums to 1
            }
            for (List<Integer> pair : map.get(key)) {
                lengths[pair.get(1)] = lengths[pair.get(0)] + 1;//update length of this diff's Arithmetic Progression
                max = Math.max(max, lengths[pair.get(1)]);
            }
        }
        return max;
    }

sd

Given a set of numbers, find theLength of theLongestArithmeticProgression (LLAP) in it. 数组可排序

Examples:

set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}

set[] = {5, 10, 15, 20, 25, 30}
output = 6
The whole set is in AP

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

Solution 1: Brute Force O(n^3)

A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set.To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n3) time.

Solution 2: DP O(n^2); O(n^2) 这个解法是假设可以排序，实际会要求不让排序。

We can solve this problem inO(n^2) time using Dynamic Programming. To get idea of the DP solution, let us first discuss solution of following simpler problem.

Given a sorted set, find if there exist three elements in Arithmetic Progression or not
Please note that, the answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]’ and ‘set[k]’ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1._How to efficiently find i and k for a given j?_We can find i and k in linear time using following simple algorithm.
1)Initialize i as j-1 and k as j+1
2)Do following while i >= 0 and j <= n-1 ..........a)If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b)If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c)Else if set[i] + set[k] < 2*set[j], then increment k (do k++). Following is C++ implementation of the above algorithm for the simpler problem.

    public static int longestArithmeticSubsequence(int[] nums) {
        if (nums.length < 3) return nums.length;
        int n = nums.length, max = 2;
        int[][] dp = new int[n][n];
        Arrays.sort(nums); // important!!
        // initialize dp[i][n - 1] = 2
        for (int i = 0; i < n; i++)
            dp[i][n - 1] = 2;
        // fix j (consider every nums[j] as second element of AP) to search for valid i & k
        for (int j = n - 2; j >= 1; j--) {
            int i = j - 1, k = j + 1;
            while (i >= 0 && k < n) {
                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;
                    max = Math.max(max, dp[i][j]);
                    i--;
                    k++;
                }
            }
            // If the loop was stopped due to k becoming more than n-1, set the remaining entties in column j as 2
            while (i >= 0) dp[i--][j] = 2;
        }
        return max;
    }