leetcode

commit 46b403d8ebf4091066e05173b7460d6f4ba7e78c
parent 5e221eb2a6a54ecc54d3560acdad4db5f56adddb
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 28 Dec 2024 23:45:22 +0100

Daily Problem

Diffstat:
A
Problems/0689.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/0689.cpp b/Problems/0689.cpp
@@ -0,0 +1,38 @@
+class Solution {
+  public:
+    vector<int> maxSumOfThreeSubarrays(const vector<int> &nums, int k) const {
+        const int n = nums.size();
+
+        static int sum[4][20003], index[4][20003];
+        static int prefix[20003];
+
+        for (int i = 1; i <= n; i++) {
+            prefix[i] = prefix[i - 1] + nums[i - 1];
+        }
+
+        memset(sum, 0x00, sizeof(sum));
+        memset(index, 0x00, sizeof(index));
+        for (int cnt = 1; cnt <= 3; cnt++) {
+            for (int end = k * cnt; end <= n; end++) {
+                const int currentSum = prefix[end] - prefix[end - k] + sum[cnt - 1][end - k];
+
+                if (currentSum > sum[cnt][end - 1]) {
+                    sum[cnt][end] = currentSum;
+                    index[cnt][end] = end - k;
+                } else {
+                    sum[cnt][end] = sum[cnt][end - 1];
+                    index[cnt][end] = index[cnt][end - 1];
+                }
+            }
+        }
+
+        int end = n;
+        vector<int> result(3, 0);
+        for (int idx = 3; idx >= 1; idx--) {
+            result[idx - 1] = index[idx][end];
+            end = result[idx - 1];
+        }
+
+        return result;
+    }
+};
diff --git a/README.md b/README.md
@@ -534,6 +534,7 @@ reference and a base for solving problems.
 |  0684  |   Medium   | [Redundant Connection](Problems/0684.cpp)                                                          |
 |  0687  |   Medium   | [Longest Univalue Path](Problems/0687.cpp)                                                         |
 |  0688  |   Medium   | [Knight Probability in Chessboard](Problems/0688.cpp)                                              |
+|  0689  |    Hard    | [Maximum Sum of 3 Non-Overlapping Subarrays](Problems/0689.cpp)                                    |
 |  0690  |   Medium   | [Employee Importance](Problems/0690.cpp)                                                           |
 |  0692  |   Medium   | [Top K Frequent Words](Problems/0692.cpp)                                                          |
 |  0695  |   Medium   | [Max Area of Island](Problems/0695.cpp)                                                            |