leetcode

commit c3b4552a426ac28b674d0611e82b7a1295c8448a
parent 4613e17661bf83905500e92f03d6a5bf1e597874
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 31 Jan 2023 15:43:09 +0100

Daily Problem

Diffstat:
A
Problems/1626.cpp
 | 
20
++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 21 insertions(+), 0 deletions(-)
diff --git a/Problems/1626.cpp b/Problems/1626.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+  int bestTeamScore(vector<int> &scores, vector<int> &ages) {
+    int n = scores.size(), res = 0;
+    vector<pair<int, int>> v(n);
+    for (int i = 0; i < n; i++) v[i] = {ages[i], scores[i]};
+    sort(v.begin(), v.end());
+
+    vector<int> dp(n, 0);
+    for (int i = 0; i < n; i++) {
+      int total = 0;
+      for (int j = 0; j < i; j++) {
+        if (v[j].second <= v[i].second) dp[i] = max(dp[i], dp[j]);
+      }
+      res = max(res, dp[i] += v[i].second);
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -314,6 +314,7 @@ for solving problems.
 |  1584  |   Medium   | [Min Cost to Connect All Points](Problems/1584.cpp)                                              |
 |  1609  |   Medium   | [Even Odd Tree](Problems/1609.cpp)                                                               |
 |  1615  |   Medium   | [Maximal Network Rank](Problems/1615.cpp)                                                        |
+|  1626  |   Medium   | [Best Team With No Conflicts](Problems/1626.cpp)                                                 |
 |  1646  |    Easy    | [Get Maximum in Generated Array](Problems/1646.cpp)                                              |
 |  1669  |   Medium   | [Merge In Between Linked Lists](Problems/1669.cpp)                                               |
 |  1672  |    Easy    | [Richest Customer Wealth](Problems/1672.cpp)                                                     |