LeetCode 673. Number of Longest Increasing Subsequence
原题链接在这里：https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/
题目：
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.
题解：
len[i] reqpresents到i的LIS长度. count[i] represents 到i的LIS个数.
Base Case 都是1.
For all j from 0 to i, if nums[j] < nums[i], there is a chance to update longest length ending at i.
If there is an update, then update len[i] with len[j]+1 and frequency = count[j].
If there is no update, but len[j]+1 == len[i] means there is other paths to construct LIS ending at i, thus accumlate frequency.
After iterating all j, if longest LIS got update, then update max length, and its frequency.
If max length stays the same, that means globally there is other LIS with the same length, accumate frequency.
Time Complexity: O(n^2), n = nums.length.
Space: O(n).
AC Java:
1 class Solution { 2 public int findNumberOfLIS(int[] nums) { 3 if(nums == null || nums.length == 0){ 4 return 0; 5 } 6 7 int n = nums.length; 8 // Longest length ending at i 9 int [] len = new int[n]; 10 11 // Frequency of longest length ending at i 12 int [] count = new int[n]; 13 int max = 1; 14 int res = 0; 15 16 for(int i = 0; i<n; i++){ 17 len[i] = 1; 18 count[i] = 1; 19 for(int j = 0; j<i; j++){ 20 if(nums[j] < nums[i]){ 21 if(len[j]+1 == len[i]){ 22 // Same longest length ending at i, accumlate frequency 23 count[i] += count[j]; 24 }else if(len[j]+1 > len[i]){ 25 // There is longer subsequence ending at i, update its longest length and frequency 26 len[i] = len[j]+1; 27 count[i] = count[j]; 28 } 29 } 30 } 31 32 if(len[i] > max){ 33 // Globally, this one is longer, update global maximum length and its requency 34 max = len[i]; 35 res = count[i]; 36 }else if(len[i] == max){ 37 // Globally, this one has the same maximum length, accumlate its frequency to res 38 res += count[i]; 39 } 40 } 41 42 return res; 43 } 44 }