leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0673.cpp (734B)

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