https://leetcode.com/problems/number-of-longest-increasing-subsequence
Problem:
Given an unsorted array of integers, find the number of longest increasing subsequence.
Example 1:
|
1 2 3 |
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:
|
1 2 3 |
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.
Idea:
Dynamic programming
Solution1:
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// Author: Huahua // Running time: 82 ms 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); // Find the length LIS. int max_len = 0; for (int i = 0; i < n; ++i) max_len = max(max_len, len(nums, i)); // Checking all endings. 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_; // c[i]: number of LIS ends with nums[i] / NLIS' vector<int> l_; // l[i]: lengeh of LIS ends with nums[i] / LIS' // Number of LIS ends with nums[n] 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); 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; } // Length of LIS ends with nums[n] int len(const vector<int>& nums, int n) { if (n == 0) return 1; if (l_[n] > 0) return l_[n]; int max_len = 1; // Check every subarray 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; } }; |
Solution2:
|
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 28 29 30 31 32 |
// Author: Huahua // Running time: 33 ms class Solution { public: int findNumberOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> c(n, 1); vector<int> l(n, 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 = *max_element(l.begin(), l.end()); int ans = 0; for (int i = 0; i < n; ++i) if (l[i] == max_len) ans += c[i]; return ans; } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment