//

// Solution128.cpp

// Algorithm

//

// Created by Pancf on 2020/12/20.

// Copyright © 2020 Pancf. All rights reserved.

//

#include "Solution128.hpp"

#include <unordered_map>

#include <algorithm>

int Solution128::longestConsecutive(std::vector<int> &nums)

{

if (!nums.size()) return 0;

int size = (int)nums.size();

std::unordered_map<int, int> mp; // key is nums[i], value is the length of sequence to which key belongs

int res = 0;

for (int i = 0; i < size; ++i) {

auto key = nums[i];

if (mp.find(key) == mp.end()) {

int left = mp.find(key - 1) != mp.end() ? mp[key - 1] : 0; // left neighbor has `left` length

int right = mp.find(key + 1) != mp.end() ? mp[key + 1] : 0; // right neighbor has `right` length

int sum = left + right + 1;

res = std::max(sum, res);

mp[key] = sum;

// Why only update mp[key - left] and mp[key + right]?

// Because only mp[key - left] and mp[key + right] has the possibility to calculate new sum

mp[key - left] = sum;

mp[key + right] = sum;

}

}

return res;

}