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表示最大递增子序列的数目,分别维护两个数组lengthsnumbers
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]+1lengths[i]=lengths[j]+1并且numbers[i] = numbers[j]。如果maxLengthlengths[i],则maxNumber加上numbers[i],否则maxLength置为lengths[i]maxNumber置为numbers[i]

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}