数组中的最长连续序列

【题目】
给定无序数组 arr, 返回其中最长的连续序列的长度.

【举例】
arr=[100,4,200,1,3,2]， 最长的连续序列为 [1,2,3,4]，所以返回 4.

【解答】

1. 使用HashMap<Integer, Integer> map，key 代表遍历过的某个数，value 代表 key 这个数所在的最长连续序列的长度。同时 map 还可以表示 arr 中的一个数之前是否出现过。
2. 从左到右遍历 arr, 假设遍历到 arr[i]。如果 arr[i] 之前出现过，直接遍历下一个数，只处理之前没出现过的 arr[i]。首先在 map 中加入记录(arr[i], 1), 代表目前 arr[i] 单独作为一个连续序列。然后分别看map中是否有arr[i]-1和arr[i]+1，如果有arr[i]-1,则把它与arr[i]合并成一个连续数列，如果有arr[i]+1,则继续把它与arr[i]合并成一个数列。
3. 遍历的过程中用全局变量 max 记录每次合并出的序列的长度最大值，最后返回 max。

【code】

import java.util.HashMap;
import java.util.Map;

public class LongestSequence {
    public int longestSequence(int[] arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int max = 1;
        //key表示遍历的某个数,value表示最长连续数列的长度
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])){
                map.put(arr[i], 1);
                if (map.containsKey(arr[i] - 1)){
                    max = Math.max(max, merge(map, arr[i] -1, arr[i]));
                }
                if (map.containsKey(arr[i] + 1)){
                    max = Math.max(max, merge(map, arr[i], arr[i] + 1));
                }
            }
        }
        return max;
    }

    //将less左边的数列与more右边的数列合并
    public int merge(Map<Integer, Integer> map, int less, int more){
        int left = less - map.get(less) + 1;
        int right = more + map.get(more) - 1;
        int len = right - left + 1;
        map.put(left, len);
        map.put(right, len);
        return len;
    }

    public static void main(String[] args) {
        int[] arr = {100, 4, 200, 1, 3, 2};
        LongestSequence longestSequence = new LongestSequence();
        System.out.println(longestSequence.longestSequence(arr));
    }
}

参考：
递归和动态规划问题：数组中的最长连续序列