leetcode

commit 9bb647b8c4088371b3152a7df519281f3ff18d28
parent 80364cba46622522bb7573ecbfd4bc246c172d70
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue,  3 Feb 2026 18:40:40 -0700

3640. trionic array 2

Diffstat:
A
trionic_array2.c
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
A
trionic_array2.py
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 91 insertions(+), 0 deletions(-)
diff --git a/trionic_array2.c b/trionic_array2.c
@@ -0,0 +1,45 @@
+// 3640. Trionic Array II
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' of length 'n'. a trionic subarray is a
+ * contiguous subarray 'nums[l ... r]' for which there exists indices 'nums[l
+ * ... p]' is stricly increasing, 'nums[p ... q]' is strictly decreasing, and
+ * 'nums[p ... r]' is strictly increasing. return the maximum sum of any trionic
+ * subarray in 'nums'.
+ */
+
+long long maxSumTrionic(int *nums, int numsSize) {
+  long long ans = LLONG_MIN, cnt = nums[0];
+  for (int l = 0, p = 0, q = 0, r = 1; r < numsSize; ++r) {
+    cnt += nums[r];
+    if (nums[r - 1] == nums[r]) {
+      l = r;
+      cnt = nums[r];
+    } else if (nums[r - 1] > nums[r]) {
+      if (r > 1 && nums[r - 2] < nums[r - 1]) {
+        p = r - 1;
+        while (l < q)
+          cnt -= nums[l++];
+        while (l + 1 < p && nums[l] < 0)
+          cnt -= nums[l++];
+      }
+    } else {
+      if (r > 1 && nums[r - 2] > nums[r - 1])
+        q = r - 1;
+      if (l < p && p < q)
+        ans = fmax(ans, cnt);
+    }
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {0, -2, -1, -3, 0, 2, -1}, n2[] = {1, 4, 2, 7};
+  long long r1 = maxSumTrionic(n1, ARRAY_SIZE(n1));
+  long long r2 = maxSumTrionic(n2, ARRAY_SIZE(n2));
+  printf("%lld\n", r1); // expect: -4
+  assert(r1 == -4);
+  printf("%lld\n", r2); // expect: 14
+  assert(r2 == 14);
+}
diff --git a/trionic_array2.py b/trionic_array2.py
@@ -0,0 +1,46 @@
+# 3640. Trionic Array II
+from itertools import pairwise
+
+"""
+you are given an integer array 'nums' of length 'n'. a trionic subarray is a
+contiguous subarray 'nums[l ... r]' for which there exists indices 'nums[l
+... p]' is stricly increasing, 'nums[p ... q]' is strictly decreasing, and
+'nums[p ... r]' is strictly increasing. return the maximum sum of any trionic
+subarray in 'nums'.
+"""
+
+
+class Solution(object):
+    def maxSumTrionic(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        l, p, q = 0, 0, 0
+        ans = len(nums), float("-inf")
+        cnt, prev = nums[0], float("inf")
+        for i, (left, right) in enumerate(pairwise(nums)):
+            if left > right:
+                cnt += right
+                if prev > left:
+                    continue
+                p = i
+                while (l < q) or (l < p - 1 and nums[l] < 0):
+                    cnt -= nums[l]
+                    l += 1
+            elif left < right:
+                cnt += right
+                if prev > left:
+                    q = i
+                if l < p < q <= i and cnt > ans:
+                    ans = cnt
+            elif left == right:
+                cnt, l = right, i + 1
+            prev = left
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maxSumTrionic(nums=[0, -2, -1, -3, 0, 2, -1]))
+    print(obj.maxSumTrionic(nums=[1, 4, 2, 7]))