public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int result = 1;
        for (int i : nums) {
            if (map.containsKey(i)) {
                continue;
            }
            int left = map.containsKey(i - 1) ? map.get(i - 1) : 0;
            int right = map.containsKey(i + 1) ? map.get(i + 1) : 0;

            int sum = left + right + 1;
            map.put(i, sum);
            result = Math.max(sum, result);
            map.put(i - left, sum);
            map.put(i + right, sum);
        }
        return result;
    }
Date 12/03/2016
@author Tushar Roy

Find longest consecutive subsequence in unsorted array.

Time complexity O(n)
Space complexity O(n)

Reference
https://leetcode.com/problems/longest-consecutive-sequence/
src/com/interview/array/LongestConsecutiveSubsequence.java