leetcode

commit 6646f95b1758ad0ff4113da8268ace6e54b2f4d0
parent 5fe98805692cf3739cb4538098b178ba6c218223
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  3 Nov 2023 19:06:38 +0000

1 Random Problem

Diffstat:
A
Problems/1031.cpp
 | 
36
++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 37 insertions(+), 0 deletions(-)
diff --git a/Problems/1031.cpp b/Problems/1031.cpp
@@ -0,0 +1,36 @@
+class Solution {
+    static int prefix[1001], suffix[1001];
+    static int n;
+
+    int solve(const int firstLen, const int secondLen) const {
+        static int left[1001], right[1001];
+
+        left[firstLen - 1] = right[n - secondLen + 1] = 0;
+        for (int i = firstLen; i <= n; i++)
+            left[i] = max(left[i - 1], prefix[i] - prefix[i - firstLen]);
+        for (int i = n - secondLen; i >= 0; i--)
+            right[i] = max(right[i + 1], suffix[i] - suffix[i + secondLen]);
+
+        int res = 0;
+        for (int i = firstLen; i <= n - secondLen; i++)
+            res = max(res, left[i] + right[i]);
+        return res;
+    }
+
+  public:
+    int maxSumTwoNoOverlap(const vector<int> &nums, int firstLen, int secondLen) const {
+        n = nums.size();
+
+        prefix[0] = 0, suffix[n] = 0;
+        for (int i = 0, acc = 0; i < n; i++)
+            prefix[i + 1] = acc += nums[i];
+        for (int i = n - 1, acc = 0; i >= 0; i--)
+            suffix[i] = acc += nums[i];
+
+        return max(solve(firstLen, secondLen), solve(secondLen, firstLen));
+    }
+};
+
+int Solution::prefix[1001];
+int Solution::suffix[1001];
+int Solution::n;
diff --git a/README.md b/README.md
@@ -506,6 +506,7 @@ for solving problems.
 |  1026  |   Medium   | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp)                                  |
 |  1027  |   Medium   | [Longest Arithmetic Subsequence](Problems/1027.cpp)                                                |
 |  1029  |   Medium   | [Two City Scheduling](Problems/1029.cpp)                                                           |
+|  1031  |   Medium   | [Maximum Sum of Two Non-Overlapping Subarrays](Problems/1031.cpp)                                  |
 |  1035  |   Medium   | [Uncrossed Lines](Problems/1035.cpp)                                                               |
 |  1038  |   Medium   | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp)                                        |
 |  1042  |   Medium   | [Flower Planting With No Adjacent](Problems/1042.cpp)                                              |