aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-08 01:43:02 -0600
committerJack Sangdahl <[email protected]>2024-09-08 01:43:02 -0600
commit06c62754e65808149019088ce0ccf4808748f5ef (patch)
treea190c217c9d725bbae0186d2641e05812186d9a0
parent228fbdfe77c140d4613b0568c1715ddc79944205 (diff)
downloadleetcode-06c62754e65808149019088ce0ccf4808748f5ef.tar.gz
leetcode-06c62754e65808149019088ce0ccf4808748f5ef.zip
1191. k-concatenation maximum sum
-rw-r--r--k_concatenation_max_sum.c46
-rw-r--r--k_concatenation_max_sum.py43
2 files changed, 89 insertions, 0 deletions
diff --git a/k_concatenation_max_sum.c b/k_concatenation_max_sum.c
new file mode 100644
index 0000000..56002db
--- /dev/null
+++ b/k_concatenation_max_sum.c
@@ -0,0 +1,46 @@
+// 1191. K-Concatenation Maximum Sum
+#include "leetcode.h"
+
+/*
+ * given an integer array 'arr' and an integer 'k', modify the array by
+ * repeating it 'k' times. for example, if 'arr = [1, 2]' and 'k = 3' then the
+ * modified array will be '[1, 2, 1, 2, 1, 2]'. return the maximum sub array sum
+ * in the modified array. note that the length of the sub array can be 0 and its
+ * sum in that case is 0. as the answer can be very large, return the answer
+ * modulo 1e9+7
+ */
+
+long long max_sum(int *arr, int arrSize) {
+ long long max = 0, sum = 0;
+ for (int i = 0; i < arrSize; i++) {
+ sum += arr[i];
+ max = sum > max ? sum : max;
+ if (sum < 0)
+ sum = 0;
+ }
+ return max;
+}
+
+int kConcatenationMaxSum(int *arr, int arrSize, int k) {
+ int mod = 1e9 + 7;
+ long long sum = 0;
+ for (int i = 0; i < arrSize; i++)
+ sum += arr[i];
+ if (k < 2)
+ return (int)(max_sum(arr, arrSize) % mod);
+ int *double_arr = (int *)malloc(arrSize * 2 * sizeof(int));
+ for (int i = 0; i < arrSize; i++) {
+ double_arr[i] = arr[i];
+ double_arr[i + arrSize] = arr[i];
+ }
+ if (sum < 0)
+ return (int)(max_sum(double_arr, arrSize * 2) % mod);
+ return (int)((max_sum(double_arr, arrSize * 2) + (k - 2) * sum) % mod);
+}
+
+int main() {
+ int a1[] = {1, 2}, a2[] = {1, -2, 1}, a3[] = {-1, -2};
+ printf("%d\n", kConcatenationMaxSum(a1, ARRAY_SIZE(a1), 3)); // expect: 9
+ printf("%d\n", kConcatenationMaxSum(a2, ARRAY_SIZE(a2), 5)); // expect: 2
+ printf("%d\n", kConcatenationMaxSum(a3, ARRAY_SIZE(a3), 7)); // expect: 0
+}
diff --git a/k_concatenation_max_sum.py b/k_concatenation_max_sum.py
new file mode 100644
index 0000000..8a28ad9
--- /dev/null
+++ b/k_concatenation_max_sum.py
@@ -0,0 +1,43 @@
+# 1191. K-Concatenation Maximum Sum
+
+"""
+given an integer array 'arr' and an integer 'k', modify the array by
+repeating it 'k' times. for example, if 'arr = [1, 2]' and 'k = 3' then the
+modified array will be '[1, 2, 1, 2, 1, 2]'. return the maximum sub array sum
+in the modified array. note that the length of the sub array can be 0 and its
+sum in that case is 0. as the answer can be very large, return the answer
+modulo 1e9+7
+"""
+
+
+class Solution(object):
+ def max_sum(self, arr):
+ curr_max, max_end = int("-inf"), 0
+ for i in arr:
+ max_end += i
+ if max_end < 0:
+ max_end = 0
+ curr_max = max(curr_max, max_end)
+ return curr_max
+
+ def kConcatenationMaxSum(self, arr, k):
+ """
+ :type arr: List[int]
+ :type k: int
+ :rtype: int
+ """
+ total = sum(arr)
+ kadane = self.max_sum(arr)
+ if k < 2:
+ return kadane(10**9 + 7)
+ if total > 0:
+ return (kadane + (k - 1) * total) % (10**9 + 7)
+ double = self.max_sum(arr * 2)
+ return double % (10**9 + 7)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kConcatenationMaxSum(arr=[1, 2], k=3))
+ print(obj.kConcatenationMaxSum(arr=[1, -2, 1], k=5))
+ print(obj.kConcatenationMaxSum(arr=[1, -2, 1], k=5))