leetcode

commit 3ccbd3c0cae091b272478445ccc427a820415346
parent e184e2cf96e080d0efe13efd05fead11e3da531f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 31 Mar 2024 13:53:43 +0000

1 Random Problem

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

2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/Problems/2909.cpp b/Problems/2909.cpp
@@ -0,0 +1,22 @@
+class Solution {
+  public:
+    int minimumSum(vector<int> &nums) const {
+        static int dp[100001];
+        const int n = size(nums);
+
+        dp[0] = nums[0];
+        for (int i = 1, mini = nums[0]; i < n; i++) {
+            dp[i] = mini = min(mini, nums[i]);
+        }
+
+        int res = INT_MAX;
+        for (int i = n - 2, mini = nums[n - 1]; i > 0; i--) {
+            if (nums[i] > dp[i - 1] && nums[i] > mini) {
+                res = min(res, nums[i] + dp[i - 1] + mini);
+            }
+            mini = min(mini, nums[i]);
+        }
+
+        return res != INT_MAX ? res : -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -1165,6 +1165,7 @@ for solving problems.
 |  2870  |   Medium   | [Minimum Number of Operations to Make Array Empty](Problems/2870.cpp)                              |
 |  2895  |   Medium   | [Minimum Processing Time](Problems/2895.cpp)                                                       |
 |  2900  |   Medium   | [Longest Unequal Adjacent Groups Subsequence I](Problems/2900.cpp)                                 |
+|  2909  |   Medium   | [Minimum Sum of Mountain Triplets II](Problems/2909.cpp)                                           |
 |  2914  |   Medium   | [Minimum Number of Changes to Make Binary String Beautiful](Problems/2914.cpp)                     |
 |  2924  |   Medium   | [Find Champion II](Problems/2924.cpp)                                                              |
 |  2938  |   Medium   | [Separate Black and White Balls](Problems/2938.cpp)                                                |