We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.
Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.
A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
so only when the next value is current value or current value + 1 we then can continue. we can use a map to store the value and the continuous length. then each time, if (current index + current value's continuous length)'s next value is equal to the current value + 1, which means we can also append this next value into the harmonious sequence. repeat this process to get the longest harmonious sequence.
Oh I am wrong...it's subsequence not the subarray. Just use a map to store the value and its count. we just need to see can we update answer by using cur value's count + cur values + 1's count.
When first seeing this problem, I thought it's a subarray problem. Therefore, I totally got a wrong direction. I try to map the index to continious same value length of this index' value.
- use a map to count the occurence of the value
- because it's subsequences, we can gather any place of this value.
- Go loop all the value in the map, add the length of value and value + 1 as the tmp answer. Compare the tmp answer with the ansewr. Each time we just do a single direction comparison to avoid duplicates comparsion like we do 3,4 for 3 will not do 3,4 for 4 again.
assume the length fo array is N
-
Time complexity: O(N)
-
Space complexity: O(N)