算法题记8----和谐数

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

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

示例 1:

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

输出: 5

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

说明: 输入的数组长度最大不超过20,000.

#include

class Solution {

public:

int findLHS(vector& nums) {

if(nums.size() < 2) return 0;

sort(nums.begin(), nums.end());

int lengthMax = 0;

int lastNum = 0 , lastAmount = 0;

int currentNum = nums[0] , currentAmount = 1;

for(int i = 1 ; i < nums.size() ; i++){

int num = nums[i];

if(num == currentNum){

currentAmount++;

}

else{

lastNum = currentNum;

lastAmount = currentAmount;

currentNum = num;

currentAmount = 1;

if(num != lastNum + 1){

lastAmount = 0;

}

}

if(lastAmount > 0){

lengthMax = max(lengthMax , currentAmount + lastAmount);

}

}

return lengthMax;

}

};