leetcode

commit ed18bdfd7d9428d3d92bbd14a2adaea517d1b87c
parent 7e6a963ee2ee8bb5d66a64201574fa5e41b108e4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 18 Feb 2023 19:47:13 +0100

Algorithm II: Day 16

Diffstat:
A
Problems/0673.cpp
 | 
22
++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/Problems/0673.cpp b/Problems/0673.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+  int findNumberOfLIS(vector<int> &nums) {
+    int n = nums.size(), res = 0, max_len = 0;
+    vector<pair<int, int>> dp(n, {1, 1});
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < i; j++) {
+        if (nums[i] > nums[j]) {
+          if (dp[i].first == dp[j].first + 1) dp[i].second += dp[j].second;
+          if (dp[i].first < dp[j].first + 1)
+            dp[i] = {dp[j].first + 1, dp[j].second};
+        }
+      }
+      if (max_len == dp[i].first) res += dp[i].second;
+      if (max_len < dp[i].first) {
+        max_len = dp[i].first;
+        res = dp[i].second;
+      }
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -269,6 +269,7 @@ for solving problems.
 |  0662  |   Medium   | [Maximum Width of Binary Tree](Problems/0662.cpp)                                                |
 |  0669  |   Medium   | [Trim a Binary Search Tree](Problems/0669.cpp)                                                   |
 |  0671  |    Easy    | [Second Minimum Node In a Binary Tree](Problems/0671.cpp)                                        |
+|  0673  |   Medium   | [Number of Longest Increasing Subsequence](Problems/0673.cpp)                                    |
 |  0684  |   Medium   | [Redundant Connection](Problems/0684.cpp)                                                        |
 |  0692  |   Medium   | [Top K Frequent Words](Problems/0692.cpp)                                                        |
 |  0695  |   Medium   | [Max Area of Island](Problems/0695.cpp)                                                          |