commit 23db1daa4e9dfaebeea9485be90e8435cf66c454
parent d9ee70a4fdca0799186b7923f2d24fc41b281b17
Author: Jack Sangdahl <jack@pngu.org>
Date: Wed, 10 Jun 2026 17:04:45 -0600
3691. maximum total subarray value 2
Diffstat:
2 files changed, 198 insertions(+), 0 deletions(-)
diff --git a/max_total_subarr_val2.c b/max_total_subarr_val2.c
@@ -0,0 +1,135 @@
+// 3691. Maximum Total Subarray Value II
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' of length 'n' and an integer 'k'. you
+ * must select exactly 'k' distinct subarrays 'nums[l ... r]' of 'nums'.
+ * subarrays may overlap, but the exact same subarrays (same 'l' and 'r') cannot
+ * be chosen more than once. the value of a subarray 'nums[l ... r]' is defined
+ * as 'max(nums[l ... r]) - min(nums[l ... r])'. the total value is the sum of
+ * the values of all chosen subarrays. return the maximum possible total value
+ * you can achieve.
+ */
+
+struct node {
+ int val;
+ int left;
+ int right;
+};
+
+struct max_heap {
+ struct node *data;
+ int size;
+};
+
+void swap(struct node *a, struct node *b) {
+ struct node tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+void push(struct max_heap *h, struct node n) {
+ h->data[++h->size] = n;
+ int i = h->size;
+ while (i > 1 && h->data[i].val > h->data[i / 2].val) {
+ swap(&h->data[i], &h->data[i / 2]);
+ i /= 2;
+ }
+}
+
+struct node pop(struct max_heap *h) {
+ struct node top = h->data[1];
+ h->data[1] = h->data[h->size--];
+ int i = 1;
+ while (2 * i <= h->size) {
+ int j = 2 * i;
+ if (j + 1 <= h->size && h->data[j + 1].val > h->data[j].val)
+ j++;
+ swap(&h->data[i], &h->data[j]);
+ i = j;
+ }
+ return top;
+}
+
+int get_max(int *seg, int left, int right, int size) {
+ int max = 0;
+ for (left += size, right += size; left <= right; left >>= 1, right >>= 1) {
+ if (left & 1) {
+ if (seg[left] > max) {
+ max = seg[left];
+ left++;
+ }
+ }
+ if (!(right & 1)) {
+ if (seg[right] > max) {
+ max = seg[right];
+ right--;
+ }
+ }
+ }
+ return max;
+}
+
+int get_min(int *seg, int left, int right, int size) {
+ int min = INT_MAX;
+ for (left += size, right += size; left <= right; left >>= 1, right >>= 1) {
+ if (left & 1) {
+ if (seg[left] < min) {
+ min = seg[left];
+ left++;
+ }
+ }
+ if (!(right & 1)) {
+ if (seg[right] < min) {
+ min = seg[right];
+ right--;
+ }
+ }
+ }
+ return min;
+}
+
+long long maxTotalValue(int *nums, int numsSize, int k) {
+ int n = 1;
+ while (n < numsSize)
+ n *= 2;
+ int *seg_max = (int *)calloc(2 * n, sizeof(int));
+ int *seg_min = (int *)malloc(2 * n * sizeof(int));
+ for (int i = 0; i < 2 * n; i++)
+ seg_min[i] = INT_MAX;
+ for (int i = 0; i < numsSize; i++)
+ seg_max[n + i] = seg_min[n + i] = nums[i];
+ for (int i = n - 1; i > 0; i--) {
+ seg_max[i] = (seg_max[2 * i] > seg_max[2 * i + 1]) ? seg_max[2 * i]
+ : seg_max[2 * i + 1];
+ seg_min[i] = (seg_min[2 * i] < seg_min[2 * i + 1]) ? seg_min[2 * i]
+ : seg_min[2 * i + 1];
+ }
+ struct max_heap h = {
+ (struct node *)malloc((numsSize + k + 1) * sizeof(struct node)), 0};
+ for (int i = 0; i < numsSize; i++) {
+ int val = get_max(seg_max, i, n - 1, n) - get_min(seg_min, i, n - 1, n);
+ push(&h, (struct node){val, i, n - 1});
+ }
+ long long ans = 0;
+ for (int i = 0; i < k; i++) {
+ struct node top = pop(&h);
+ ans += top.val;
+ if (top.right > top.left) {
+ int val = get_max(seg_max, top.left, top.right - 1, n) -
+ get_min(seg_min, top.left, top.right - 1, n);
+ push(&h, (struct node){val, top.left, top.right - 1});
+ }
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 3, 2}, n2[] = {4, 2, 5, 1};
+ long long r1 = maxTotalValue(n1, ARRAY_SIZE(n1), 2);
+ long long r2 = maxTotalValue(n2, ARRAY_SIZE(n2), 3);
+ printf("%lld\n", r1);
+ assert(r1 == 4);
+ printf("%lld\n", r2);
+ assert(r2 == 12);
+}
diff --git a/max_total_subarr_val2.py b/max_total_subarr_val2.py
@@ -0,0 +1,63 @@
+# 3691. Maximum Total Subarray Value II
+import heapq
+
+"""
+you are given an integer array 'nums' of length 'n' and an integer 'k'. you
+must select exactly 'k' distinct subarrays 'nums[l ... r]' of 'nums'.
+subarrays may overlap, but the exact same subarrays (same 'l' and 'r') cannot
+be chosen more than once. the value of a subarray 'nums[l ... r]' is defined
+as 'max(nums[l ... r]) - min(nums[l ... r])'. the total value is the sum of
+the values of all chosen subarrays. return the maximum possible total value
+you can achieve.
+"""
+
+
+class Solution:
+ def maxTotalValue(self, nums: List[int], k: int) -> int:
+ n, size = len(nums), 1
+ while size < n:
+ size *= 2
+ seg_max = [0] * (2 * size)
+ seg_min = [10**18] * (2 * size)
+ for i in range(n):
+ seg_max[size + i] = nums[i]
+ seg_min[size + i] = nums[i]
+ for i in range(size - 1, 0, -1):
+ seg_max[i] = max(seg_max[2 * i], seg_max[2 * i + 1])
+ seg_min[i] = min(seg_min[2 * i], seg_min[2 * i + 1])
+
+ def query(l, r):
+ l += size
+ r += size
+ mx, mn = 0, 10**18
+ while l <= r:
+ if l % 2 == 1:
+ mx = max(mx, seg_max[l])
+ mn = min(mn, seg_min[l])
+ l += 1
+ if r % 2 == 0:
+ mx = max(mx, seg_max[r])
+ mn = min(mn, seg_min[r])
+ r -= 1
+ l //= 2
+ r //= 2
+ return mx - mn
+
+ heap = []
+ for l in range(n):
+ val = query(l, n - 1)
+ heapq.heappush(heap, (-val, l, n - 1))
+ ans = 0
+ for _ in range(k):
+ val, l, r = heapq.heappop(heap)
+ ans += -val
+ if r > l:
+ new_val = query(l, r - 1)
+ heapq.heappush(heap, (-new_val, l, r - 1))
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxTotalValue(nums=[1, 3, 2], k=2))
+ print(obj.maxTotalValue(nums=[4, 2, 5, 1], k=3))
