LongestHarmoniousSubsequence [source code]

public class LongestHarmoniousSubsequence {
static

public class Solution {
    public int findLHS(int[] nums) {
        if (nums.length == 0) return 0;
        int min = nums[0], max = nums[0];
        for (int i : nums) {
            if (i < min) min = i;
            else if (i > max) max = i;
        }
        int[] counts = new int[max - min + 1];
        for (int i : nums) counts[i - min]++;
        int maxLen = 0;
        for (int i = 1; i < counts.length; ) {
            if (counts[i] > 0) {
                if (counts[i - 1] > 0 && counts[i] + counts[i - 1] > maxLen) maxLen = counts[i] + counts[i - 1];
                i++;
            } else i += 2;
        }
        return maxLen;
    }
}

    public static void main(String[] args) {
        LongestHarmoniousSubsequence.Solution tester = new LongestHarmoniousSubsequence.Solution();
        int[] input1 = {1,3,2,2,5,2,3,7};//5
        int[] input2 = {1,3,5,7,9,11,13,15,17};//0
        int[] input3 = {4289383,46930886,81692777,14636915,57747793,24238335,19885386,49760492,96516649,89641421};//0
        System.out.println(tester.findLHS(input3));
    }
}

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
这个以前讲过了, subseq 是可以不连续的;

这个题目总体来说还是不难的. 一开始看到这种 subseq 的问题, 就享用类似 Kadane 那种类似DP 的思路来解决. 不过这里的 subseq 是可以不连续的, 所以这个问题就是一个 counts 题而已.

这个算法总体来说应该还是好的, 而且用 hashing 的思路的话, 连 counts 统计完了之后的排序都省略了; 但是 OJ 这里好像故意埋了坑:
[4289383,46930886,81692777,14636915,57747793,24238335,19885386,49760492,96516649,89641421]
这个 case 的话, 直接就是Memory Limit Exceeded.

Problem Description

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Note: The length of the input array will not exceed 20,000.

Difficulty:Easy
Category:Algorithms
Acceptance:39.79%
Contributor: love_Fawn
Companies
liveramp
Related Topics
hash table