leetcode

commit 326c90948b13f48ca27456cad53d15f80306e826
parent 5ceb3e5ec284aa4980a9367f65c377f83370590c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 31 Jan 2026 19:54:38 -0700

3010. divide an array into subarrays with minimum cost 1

Diffstat:
A
divide_arr_subarr_min_cost1.c
 | 
28
++++++++++++++++++++++++++++
A
divide_arr_subarr_min_cost1.py
 | 
30
++++++++++++++++++++++++++++++

2 files changed, 58 insertions(+), 0 deletions(-)
diff --git a/divide_arr_subarr_min_cost1.c b/divide_arr_subarr_min_cost1.c
@@ -0,0 +1,28 @@
+// 3010. Divide an Array Into Subarrays With Minimum Cost I
+#include "leetcode.h"
+
+/*
+ * you are given an array of integers 'nums' of length 'n'. the cost of an array
+ * is the value of its first element. you need to divide 'nums' into 3 disjoint
+ * contiguous subarrays. return the minimum possible sum of the cost of these
+ * subarrays.
+ */
+
+int minimumCost(int *nums, int numsSize) {
+  int sum = nums[0], min1 = INT_MAX, min2 = INT_MAX;
+  for (int i = 1; i < numsSize; i++) {
+    if (nums[i] < min1) {
+      min2 = min1;
+      min1 = nums[i];
+    } else if (nums[i] < min2 && nums[i] >= min1)
+      min2 = nums[i];
+  }
+  return sum + min1 + min2;
+}
+
+int main() {
+  int n1[] = {1, 2, 3, 12}, n2[] = {5, 4, 3}, n3[] = {10, 3, 1, 1};
+  printf("%d\n", minimumCost(n1, ARRAY_SIZE(n1))); // expect: 6
+  printf("%d\n", minimumCost(n2, ARRAY_SIZE(n2))); // expect: 12
+  printf("%d\n", minimumCost(n3, ARRAY_SIZE(n3))); // expect: 12
+}
diff --git a/divide_arr_subarr_min_cost1.py b/divide_arr_subarr_min_cost1.py
@@ -0,0 +1,30 @@
+# 3010. Divide an Array Into Subarrays With Minimum Cost I
+import heapq
+
+"""
+you are given an array of integers 'nums' of length 'n'. the cost of an array
+is the value of its first element. you need to divide 'nums' into 3 disjoint
+contiguous subarrays. return the minimum possible sum of the cost of these
+subarrays.
+"""
+
+
+class Solution(object):
+    def minimumCost(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        h = []
+        heapq.heappush(h, -nums[1])
+        heapq.heappush(h, -nums[2])
+        for i in nums[3:]:
+            heapq.heappushpop(h, -i)
+        return nums[0] - h[0] - h[1]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minimumCost(nums=[1, 2, 3, 12]))
+    print(obj.minimumCost(nums=[5, 4, 3]))
+    print(obj.minimumCost(nums=[10, 3, 1, 1]))