diff options
Diffstat (limited to 'num_longest_incr_subseq.cpp')
-rw-r--r-- | num_longest_incr_subseq.cpp | 53 |
1 files changed, 0 insertions, 53 deletions
diff --git a/num_longest_incr_subseq.cpp b/num_longest_incr_subseq.cpp deleted file mode 100644 index bf6529b..0000000 --- a/num_longest_incr_subseq.cpp +++ /dev/null @@ -1,53 +0,0 @@ -// 673. Number of Longest Increasing Subsequence -#include "leetcode.h" - -/* - * given an integer array 'nums', return the number of longest increasing - * subsequences. notice that the sequence has to strictly increasing. - */ - -class Solution { -public: - int findNumberOfLIS(vector<int> &nums) { - if (nums.empty()) - return 0; - vector<vector<pair<int, int>>> dyn(nums.size() + 1); - int curr_max = 0; - for (int i = 0; i < nums.size(); ++i) { - int l = 0, r = curr_max; - while (l < r) { - int mid = l + (r - l) / 2; - if (dyn[mid].back().first < nums[i]) - l = mid + 1; - else - r = mid; - } - int options = 1, row = l - 1; - if (row >= 0) { - int l1 = 0, r1 = dyn[row].size(); - while (l1 < r1) { - int mid = l1 + (r1 - l1) / 2; - if (dyn[row][mid].first < nums[i]) - r1 = mid; - else - l1 = mid + 1; - } - options = dyn[row].back().second; - options -= !l1 ? 0 : dyn[row][l1 - 1].second; - } - dyn[l].push_back( - {nums[i], - (dyn[l].empty() ? options : dyn[l].back().second + options)}); - if (l == curr_max) - curr_max++; - } - return dyn[curr_max - 1].back().second; - } -}; - -int main() { - Solution obj; - vector<int> n1 = {1, 3, 5, 4, 7}, n2 = {2, 2, 2, 2, 2}; - printf("%d\n", obj.findNumberOfLIS(n1)); // expect: 2 - printf("%d\n", obj.findNumberOfLIS(n2)); // expect: 5 -} |