Longest Harmonious Subsequence

🏠 ⬅️ ➡️

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.

Example 1:

Input: nums = [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Example 2:

Input: nums = [1,2,3,4] Output: 2

Example 3:

Input: nums = [1,1,1,1] Output: 0

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -109 <= nums[i] <= 109
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem "Harmonious Array"
    implicit none

    integer, parameter :: n = 8
    integer, dimension(n) :: nums
    integer :: i, j, max_diff, min_diff
    integer :: longest_harmonious_subsequence

    ! Examples
    nums = [1, 3, 2, 2, 5, 2, 3, 7]
    write (*, '(a, i0)') 'Example 1: ', longest_harmonious_subsequence(nums)
    nums = [1, 2, 3, 4]
    write (*, '(a, i0)') 'Example 2: ', longest_harmonious_subsequence(nums)
    nums = [1, 1, 1, 1]
    write (*, '(a, i0)') 'Example 3: ', longest_harmonious_subsequence(nums)

contains

    function longest_harmonious_subsequence(nums) result(max_len)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: max_len, len, i, j

        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (abs(nums(j) - nums(i)) == 1) then
                    len = len + 1
                end if
            end do
            if (len > max_len) then
                max_len = len
            end if
            len = 0
        end do
    end function longest_harmonious_subsequence

end program main
❌ Compiled
❌ Executed
❌ Correct 
```
program longest_harmonious_subsequence
    implicit none

    integer, parameter :: INT_MAX = huge(1)
    integer, parameter :: INT_MIN = -huge(1)

    integer, dimension(:), allocatable :: nums
    integer :: n, i, j, max_diff, diff
    integer :: longest_subsequence

    ! Read the number of elements in the array
    read(*,*) n

    ! Allocate memory for the array
    allocate(nums(n))

    ! Read the elements of the array
    do i = 1, n
        read(*,*) nums(i)
    end do

    ! Initialize the maximum difference and the longest subsequence
    max_diff = 0
    longest_subsequence = 0

    ! Iterate over the elements of the array
    do i = 1, n - 1
        ! Iterate over the remaining elements of the array
        do j = i + 1, n
            ! Calculate the difference between the current element and the next element
            diff = abs(nums(i) - nums(j))

            ! If the difference is greater than the maximum difference, update the maximum difference
            if (diff > max_diff) then
                max_diff = diff
            end if

            ! If the difference is exactly 1, update the longest subsequence
            if (diff == 1) then
                longest_subsequence = longest_subsequence + 1
            end if
        end do
    end do

    ! Print the longest harmonious subsequence
    write(*,*) longest_subsequence

    ! Deallocate the memory for the array
    deallocate(nums)
end program longest_harmonious_subsequence
```
🌐 Data from online sources 
def findLHS(nums):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1

    longest_sequence = 0
    for key in count:
        if key + 1 in count:
            longest_sequence = max(longest_sequence, count[key] + count[key + 1])

    return longest_sequence
  1. Create a hashmap to count the occurrences of each number in the input array.
  2. Iterate through the uniquq elements in the hashmap.
  3. For each element, check if there exists an element that is 1 greater, and if so, record the sum of the element count and the count of the element 1 greater.
  4. Keep track of the maximum harmony sequence found during this iteration.
  5. Return the length of the longest harmonious sequence found.
🌐 Data from online sources 
#include <vector>
#include <unordered_map>
using namespace std;

int findLHS(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int num : nums)
        count[num]++;

    int longest_sequence = 0;
    for (auto &elem : count) {
        if (count.find(elem.first + 1) != count.end())
            longest_sequence = max(longest_sequence, elem.second + count[elem.first + 1]);
    }

    return longest_sequence;
}
  1. Create a hashmap to count the occurrences of each number in the input array.
  2. Iterate through the uniquq elements in the hashmap.
  3. For each element, check if there exists an element that is 1 greater, and if so, record the sum of the element count and the count of the element 1 greater.
  4. Keep track of the maximum harmony sequence found during this iteration.
  5. Return the length of the longest harmonious sequence found.