[leetcode][594] Longest Harmonious Subsequence.cpp

문제 : leetcode.com/problems/longest-harmonious-subsequence/

---

배열이 주어질 때, 최대값과 최소값이 정확히 1차이가 나는 subsequence들의 최대 길이를 구해라.

---

결국 길이가 1차이나는 요소들의 발생횟수들의 합의 최대값을 구하는 문제.

배열을 탐색하면서 요소 값을 key, 나온 횟수를 value로 가지는 map을 만들어 갱신한다.

map을 모두 채웠으면 map을 모두 탐색하면서 탐색중인 map의 key값 + 1을 map에서 찾아서 만약 없으면 최대, 최소 차이가 1인 서브시퀀스를 만들수 없으므로 다음 map요소를 탐색한다. 만일 있다면 map[key] + map[key+1] 한 값들의 최대값을 구하면 정답이 된다.

 

시간복잡도는 O(N). N은 배열의 길이.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/594.%20Longest%20Harmonious%20Subsequence.cpp

---

map<int, int> m;
for(map<int,int>::iterator it = m.begin();
    it != m.end(); it++) {
    int first = it->first;
    int second = it->second;
     //...
}

map<int, int> m;
for(auto now: m) {
   int first = now.first;
   int second = now.second;
     //...
}

iterator 반복문 항상 위에처럼 썼었는데 아래처럼 auto 쓰면 for문 쉽게 접근 가능하구나. 개꿀.