leetcode

commit 67e438adf3a29f760c8fac1c3138a66cd134d26e
parent 5bc60693541116e0de9ab6b0d91ae47d13e2e7cc
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 26 Nov 2025 21:53:24 -0700

3381. maximum subarray sum with length divisible by k

Diffstat:
A
maximum_subarr_sum_len_div_k.c
 | 
30
++++++++++++++++++++++++++++++
A
maximum_subarr_sum_len_div_k.py
 | 
30
++++++++++++++++++++++++++++++

2 files changed, 60 insertions(+), 0 deletions(-)
diff --git a/maximum_subarr_sum_len_div_k.c b/maximum_subarr_sum_len_div_k.c
@@ -0,0 +1,30 @@
+// 3381. Maximum Subarray Sum With Length Divisible by K
+#include "leetcode.h"
+
+/*
+ * you are given an array of integers 'nums' and an integer 'k'. return the
+ * maximum sum of a subarray of 'nums', such that the size of the subarray is
+ * divisble by 'k'.
+ */
+
+long long maxSubarraySum(int *nums, int numsSize, int k) {
+  long long ans = LLONG_MIN, total = 0;
+  long long *pre = (long long *)malloc(k * sizeof(long long));
+  for (int i = 0; i < k; i++)
+    pre[i] = LLONG_MAX / 2;
+  pre[k - 1] = 0;
+  for (int i = 0; i < numsSize; i++) {
+    total += nums[i];
+    ans = fmax(ans, total - pre[i % k]);
+    pre[i % k] = fmin(pre[i % k], total);
+  }
+  free(pre);
+  return ans;
+}
+
+int main() {
+  int n1[] = {1, 2}, n2[] = {-1, -2, -3, -4, -5}, n3[] = {-5, 1, 2, -3, 4};
+  printf("%lld\n", maxSubarraySum(n1, ARRAY_SIZE(n1), 1)); // expect: 3
+  printf("%lld\n", maxSubarraySum(n2, ARRAY_SIZE(n2), 4)); // expect: -10
+  printf("%lld\n", maxSubarraySum(n3, ARRAY_SIZE(n3), 2)); // expect: 4
+}
diff --git a/maximum_subarr_sum_len_div_k.py b/maximum_subarr_sum_len_div_k.py
@@ -0,0 +1,30 @@
+# 3381. Maximum Subarray Sum With Length Divisible by K
+from itertools import accumulate
+
+"""
+you are given an array of integers 'nums' and an integer 'k'. return the
+maximum sum of a subarray of 'nums', such that the size of the subarray is
+divisble by 'k'.
+"""
+
+
+class Solution(object):
+    def maxSubarraySum(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: int
+        """
+        pre, ans = k * [float("inf")], float("-inf")
+        pre[-1] = 0
+        for i, j in enumerate(accumulate(nums)):
+            ans = max(ans, j - pre[i % k])
+            pre[i % k] = min(pre[i % k], j)
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.maxSubarraySum(nums=[1, 2], k=1))
+    print(obj.maxSubarraySum(nums=[-1, -2, -3, -4, -5], k=4))
+    print(obj.maxSubarraySum(nums=[-5, 1, 2, -3, 4], k=2))