We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly
Given an integer array
A subsequence of the 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.
1
.Given an integer array
nums
, return the length of its longest harmonious subsequence among all its possible subsequences.A subsequence of the 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].
Approach
Java
import java.util.HashMap;public class HLS {public static void main(String[] args) {int[] nums = { 1, 3, 2, 2, 5, 2, 3, 7 };System.out.println(findLHS(nums));}static int findLHS(int[] nums) {int ans = 0;HashMap<Integer, Integer> ump = new HashMap<Integer, Integer>();// count frequency of each elementsfor (int i : nums) {ump.put(i, ump.getOrDefault(i, 0) + 1);}// iterate for all elementsfor (Integer i : ump.keySet()) {int a = ump.getOrDefault(i - 1, 0);int b = ump.getOrDefault(i + 1, 0);if (a > 0 || b > 0)ans = Math.max(ans, ump.get(i) + Math.max(a, b));}return ans;}}
C++
#include <bits/stdc++.h>using namespace std;int findLHS(vector<int> &nums){int ans = 0;unordered_map<int, int> ump;//count frequency of each elementsfor (int i : nums){ump[i]++;}//iterate for all elementsfor (int i = 0; i < nums.size(); i++){int a = ump[nums[i] - 1];int b = ump[nums[i] + 1];if (a > 0 || b > 0)ans = max(ans, ump[nums[i]] + max(a, b));}return ans;}int main(){vector<int> nums = {1, 3, 2, 2, 5, 2, 3, 7};cout << findLHS(nums);return 0;}
No comments:
Post a Comment