LeetCode 673. Number of Longest Increasing Subsequence

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/10/17/LeetCode-673-Number-of-Longest-Increasing-Subsequence/

访问原文「LeetCode 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.

题意解析

给一个数组，求出数组中最长递增子序列的个数，子序列不要求连续。

解法分析

maxLength表示最大递增子序列的长度，maxNumber表示最大递增子序列的数目，分别维护两个数组lengths、numbers。
lengths[i]表示包含第i个数字的最大递增子序列的长度；numbers[i]表示包含第i个数字的最大递增子序列的个数。
求第i个数字时，用j(0<j<i)开始遍历，nums[i]>nums[j]时，如果lengths[i]==lengths[j]+1，则numbers[i] += numbers[j]，如果lengths[i]<lengths[j]+1，lengths[i]=lengths[j]+1并且numbers[i] = numbers[j]。如果maxLength为lengths[i]，则maxNumber加上numbers[i]，否则maxLength置为lengths[i]，maxNumber置为numbers[i]。

解题代码

public int findNumberOfLIS(int[] nums) {
    int numLength = nums.length;
    int maxNumber = 0;
    int maxLength = 0;
    int[] lengths =  new int[numLength];
    int[] numbers = new int[numLength];
    for(int i = 0; i<numLength; i++){
        lengths[i] = numbers[i] = 1;
        for(int j = 0; j <i ; j++){
            if(nums[i] > nums[j]){
                if(lengths[i] == lengths[j] + 1)numbers[i] += numbers[j];
                if(lengths[i] < lengths[j] + 1){
                    lengths[i] = lengths[j] + 1;
                    numbers[i] = numbers[j];
                }
            }
        }
        if(maxLength == lengths[i]){
            maxNumber += numbers[i];
        }
        if(maxLength < lengths[i]){
            maxLength = lengths[i];
            maxNumber = numbers[i];
        }
    }
    return maxNumber;
}