673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]

Output: 2

Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]

Output: 5

Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Approach #1: C++. [DFS]

class Solution {

public:

    int findNumberOfLIS(vector<int>& nums) {

        int n = nums.size();

        if (n == 0) return 0;

        c_ = vector<int>(n, 0);

        l_ = vector<int>(n, 0);

        int max_len = 0;

        for (int i = 0; i < n; ++i)

            max_len = max(max_len, len(nums, i));

        int ans = 0;

        for (int i = 0; i < n; ++i)

            if (len(nums, i) == max_len)

                ans += count(nums, i);

        return ans;

    }

private:

    vector<int> c_;

    vector<int> l_;

    // find the total number of increasing subsequence from i to n of the index.

    int count(const vector<int>& nums, int n) {

        if (n == 0) return 1;

        if (c_[n] > 0) return c_[n];

        int total_count = 0;

        int l = len(nums, n);

        // find the number of increasing subsequence which is short than current subsquence.

        for (int i = 0; i < n; ++i)

            if (nums[n] > nums[i] && len(nums, i) == l-1)

                total_count += count(nums, i);

        if (total_count == 0)

            total_count = 1;

        return c_[n] = total_count;

    }

    // find the max length of increasing subsequence from i to n of the index.

    int len(const vector<int>& nums, int n) {

        if (n == 0) return 1;

        if (l_[n] > 0) return l_[n];

        int max_len = 1;

        for (int i = 0; i < n; ++i)

            if (nums[n] > nums[i])

                max_len = max(max_len, len(nums, i) + 1);

        return l_[n] = max_len;

    }

};

Appraoch #2: Interation. [Java]

class Solution {

    public int findNumberOfLIS(int[] nums) {

        int n = nums.length;

        if (n == 0) return 0;

        int[] c = new int[n];

        int[] l = new int[n];

        Arrays.fill(c, 1);

        Arrays.fill(l, 1);

        for (int i = 1; i < n; ++i) {

            for (int j = 0; j < i; ++j) {

                if (nums[i] > nums[j])

                    if (l[j] + 1 > l[i]) {

                        l[i] = l[j] + 1;

                        c[i] = c[j];

                    } else if (l[j] + 1 == l[i]){

                        c[i] += c[j];

                    }

            }

        }

        int max_len = 0;

        for (int i = 0; i < n; ++i)

            if (l[i] > max_len)

                max_len = l[i];

        int ans = 0;

        for (int i = 0; i < n; ++i) {

            if (l[i] == max_len)

                ans += c[i];

        }

        return ans;

    }

}

Analysis:

The idea is to use two arrays l[n] ans c[n] to record the maximum length os Incresing Subsequence ans the coresponding number of there sequence which ends with nums[i], respectively. That is:

l[i]: the lenght of the Longest Increasing Subseuqence which ends with nums[i].

c[i]: the number of the Longest Increasing Subsequence which ends with nums[i].

Then, the result is the sum of each c[i] while its corresponding l[i] is the maximum length.

Reference:

https://leetcode.com/problems/number-of-longest-increasing-subsequence/discuss/107293/JavaC%2B%2B-Simple-dp-solution-with-explanation

http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-673-number-of-longest-increasing-subsequence/

巴特西

673. Number of Longest Increasing Subsequence

最新文章

热门文章