leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0673.cpp (734B)

0 class Solution { 1 public: 2 int findNumberOfLIS(vector<int> &nums) { 3 int n = nums.size(), res = 0, max_len = 0; 4 vector<pair<int, int>> dp(n, {1, 1}); 5 for (int i = 0; i < n; i++) { 6 for (int j = 0; j < i; j++) { 7 if (nums[i] > nums[j]) { 8 if (dp[i].first == dp[j].first + 1) dp[i].second += dp[j].second; 9 if (dp[i].first < dp[j].first + 1) dp[i] = {dp[j].first + 1, dp[j].second}; 10 } 11 } 12 if (max_len == dp[i].first) res += dp[i].second; 13 if (max_len < dp[i].first) { 14 max_len = dp[i].first; 15 res = dp[i].second; 16 } 17 } 18 return res; 19 } 20 };