Clicking Exercise - 64 Longest Harmonic Subsequences

64 最长和谐子序列

1.问题描述
Harmony refers to an array an array（长度>=2）Elements in the difference between the maximum and the minimum is just1.

现在,给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度.

If you can't find such an array,则输出0.

示例 :

输入: [1,3,2,2,5,2,3,7]

输出: 5

原因: 最长的和谐数组是：[3,2,2,2,3].

说明: Input array length is more than20,000.
2.输入说明
First of all, the length of the input integer arrayn,2<=n<=10000

然后输入n个整数,以空格分隔.
3.输出说明
The length of the output of the longest harmonious subsequence
4.范例
输入
8
1 3 2 2 5 2 3 7
输出
5
5.代码

#include<iostream>
#include<map>
#include<string>
#include<unordered_map>
#include<algorithm>
#include<string.h>//memset函数
using namespace std;

int maxLen(vector<int> nums)
{
    
	unordered_map<int, int>hash;
	int ans = 0;
	for (int num : nums)
		hash[num]++;
	for (int i=0;i<nums.size();i++)
	{
    
		if (hash[nums[i]] && hash[nums[i] + 1])//若nums[i]和nums[i]+1都存在
		{
    
			ans = max(ans, hash[nums[i]] + hash[nums[i] + 1]);
		}
	}
	return ans;
}


int main()

{
    
	int n,tmp;
	cin >> n;
	vector<int> nums;
	for (int i = 0; i < n; i++)
	{
    
		cin >> tmp;
		nums.push_back(tmp);
	}
	int res = maxLen(nums);
	cout << res << endl;
	return 0;
}