leetcode

commit a368c17075901e48b1497d86737b00da31a8c11d
parent 622aee9981e9952b07796f994c7395163e5bffdd
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 22 Mar 2024 18:10:19 +0000

1 Random Problem

Diffstat:
A
Problems/0813.cpp
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 49 insertions(+), 0 deletions(-)
diff --git a/Problems/0813.cpp b/Problems/0813.cpp
@@ -0,0 +1,48 @@
+
+// Recursive
+class Solution {
+    static double dp[101][101];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    double largestSumOfAverages(const vector<int> &nums, int k, int c = 0) {
+        if (k == 0) return c == size(nums) ? 0 : -100000;
+        if (dp[k][c] == dp[k][c]) return dp[k][c];
+
+        double res = 0, sum = 0;
+        for (int i = c, j = 1; i < size(nums); i++, j++) {
+            sum += nums[i];
+            res = max(res, sum / j + largestSumOfAverages(nums, k - 1, i + 1));
+        }
+
+        return dp[k][c] = res;
+    }
+};
+
+double Solution::dp[101][101];
+
+// Bottom-up DP
+class Solution {
+    static double dp[101][101];
+
+  public:
+    double largestSumOfAverages(const vector<int> &nums, int k, int c = 0) {
+        static double sum[101], dp[101];
+        const int n = size(nums);
+
+        for (int i = 0, acc = 0; i < n; i++)
+            sum[i + 1] = acc += nums[i];
+        for (int i = 0; i < n; i++)
+            dp[i] = (sum[n] - sum[i]) / (n - i);
+
+        while (--k) {
+            for (int i = 0; i < n; i++) {
+                for (int j = i + 1; j < n; j++) {
+                    dp[i] = max(dp[i], dp[j] + (sum[j] - sum[i]) / (j - i));
+                }
+            }
+        }
+
+        return dp[0];
+    }
+};
diff --git a/README.md b/README.md
@@ -486,6 +486,7 @@ for solving problems.
 |  0807  |   Medium   | [Max Increase to Keep City Skyline](Problems/0807.cpp)                                             |
 |  0808  |   Medium   | [Soup Servings](Problems/0808.cpp)                                                                 |
 |  0811  |   Medium   | [Subdomain Visit Count](Problems/0811.cpp)                                                         |
+|  0813  |   Medium   | [Largest Sum of Averages](Problems/0813.cpp)                                                       |
 |  0814  |   Medium   | [Binary Tree Pruning](Problems/0814.cpp)                                                           |
 |  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                    |
 |  0816  |   Medium   | [Ambiguous Coordinates](Problems/0816.cpp)                                                         |