# Python, Straightforward with Explanation

• Let `count[x]` be the number of `x`'s in our array.
Suppose our longest subsequence `B` has `min(B) = x` and `max(B) = x+1`.
Evidently, it should use all occurrences of `x` and `x+1` to maximize it's length, so `len(B) = count[x] + count[x+1]`.
Additionally, it must use `x` and `x+1` atleast once, so `count[x]` and `count[x+1]` should both be positive.

``````def findLHS(self, A):
count = collections.Counter(A)
ans = 0
for x in count:
if x+1 in count:
ans = max(ans, count[x] + count[x+1])
return ans
``````

Alternatively, we can count values in a straightforward way using a dictionary: replacing our first line of `count = collections.Counter(A)` with:

``````count = {}
for x in A:
count[x] = count.get(x, 0) + 1
``````

• @awice your codes are very convenient and efficiency , and the answers are all right in my PC. But on the leetcode , the iteration of ''' for x in count ''' only iterate one time, could you tell me the reason? Thank you :)

• @Jaylan count is a dictionary mapping values in our array to the number of times they occur. For example, if our array is `A = [1, 1, 1, 2, 5, 5, 5]`, then our dictionary will be `count = {1: 3, 2: 1, 5: 3}`. When we iterate over count, we iterate over it's keys. So `for x in count` will loop through it's inner block three times, with the variable `x = 1, x = 2,` and `x = 5`.

• The same:

``````def findLHS(self, nums):
c = collections.Counter(nums)
return max(c[x] + c[x + 1] if c[x + 1] else 0 for x in c) if nums else 0``````

• Is the time complexity O(n)? and how to return the sub sequence array

• This post is deleted!

• @retrocodr The code below gives you the subsequence and it's O(n). Since we know which number can be used as the LHS, we can record this number and find out the subsequence by looking the array again.

``````class Solution(object):
def findLHS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
ansNum = None
d = collections.Counter(nums)
for num in nums:
if num + 1 in d:
if d[num] + d[num + 1] > ans:
ans = d[num] + d[num + 1]
ansNum = num
res = []
for num in nums:
if num in [ansNum, ansNum + 1]:
res.append(num)
return ans
``````

• ans
This doesn't seem to preserve the original order, does it? I thought subsequence needs to maintain original element's order, only to remove certain elements.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.