Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1191.html
1191. K-Concatenation Maximum Sum
Level
Medium
Description
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 10^9 + 7
.
Example 1:
Input: arr = [1,2], k = 3
Output: 9
Example 2:
Input: arr = [1,-2,1], k = 5
Output: 2
Example 3:
Input: arr = [-1,-2], k = 7
Output: 0
Constraints:
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
Solution
First calculate the maximum subarray sum in arr
without repeating. This can be achieved using the solution to problem 53. If k == 1
, simply return the maximum subarray sum.
Then calculate the sum of all the elements of arr
, the maximum prefix sum of arr
and the maximum postfix sum of arr
. All the sums are calculated in the single arr
without repeating. Update the maximum sum by the maximum subarray sum and the sum of the maximum postfix sum and the maximum prefix sum. If the sum of all the elements of arr
is greater than 0, then update the maximum sum using the following information: the sum of all the elements of arr
multiplied by k
, the maximum postfix sum plus the sum of all the elements of arr
multiplied by k - 2
plus the maximum prefix sum, the maximum postfix sum plus the sum of all the elements of arr
multiplied by k - 1
, and the sum of all the elements of arr
multiplied by k - 1
plus the maximum prefix sum. Finally, rethrn the maximum sum.
-
class Solution { public int kConcatenationMaxSum(int[] arr, int k) { final int MODULO = 1000000007; long maxSubArraySum = maxSubArraySum(arr); if (k == 1) return (int) (maxSubArraySum % MODULO); long sum = 0; long maxPrefixSum = 0; int length = arr.length; for (int i = 0; i < length; i++) { sum += arr[i]; maxPrefixSum = Math.max(maxPrefixSum, sum); } long postfixSum = 0, maxPostfixSum = 0; for (int i = length - 1; i >= 0; i--) { postfixSum += arr[i]; maxPostfixSum = Math.max(maxPostfixSum, postfixSum); } long maxSum = Math.max(maxSubArraySum, maxPostfixSum + maxPrefixSum); if (sum > 0) { maxSum = Math.max(maxSum, sum * k); maxSum = Math.max(maxSum, maxPostfixSum + sum * (k - 2) + maxPrefixSum); maxSum = Math.max(maxSum, Math.max(sum * (k - 1) + maxPrefixSum, maxPostfixSum + sum * (k - 1))); } return (int) (maxSum % MODULO); } public long maxSubArraySum(int[] arr) { int length = arr.length; long newSum = arr[0], max = arr[0]; for (int i = 1; i < length; i++) { newSum = Math.max(newSum + arr[i], arr[i]); max = Math.max(max, newSum); } max = Math.max(max, 0); return max; } }
-
// OJ: https://leetcode.com/problems/k-concatenation-maximum-sum/ // Time: O(N) // Space: O(1) // Ref: https://leetcode.com/problems/k-concatenation-maximum-sum/discuss/382885/Short-and-concise-O(N)-C%2B%2B-solution class Solution { public: int kConcatenationMaxSum(vector<int>& A, int k) { long N = A.size(), sum = A[0], mx = A[0], total = accumulate(begin(A), end(A), 0L), mod = 1e9 + 7; for (int i = 1; i < N * min(k, 2); ++i) { sum = max((long)A[i % N], sum + A[i % N]); mx = max(mx, sum); } return max({ 0L, mx, total * max(0, k - 2) + mx }) % mod; } };
-
# 1191. K-Concatenation Maximum Sum # https://leetcode.com/problems/k-concatenation-maximum-sum/ class Solution: def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: M = 10 ** 9 + 7 def kadane(arr, res = 0, curr = 0): for num in arr: curr = max(num, curr + num) res = max(res, curr) return res return ((k - 2) * max(sum(arr), 0) + kadane(arr * 2) if k > 1 else kadane(arr)) % M
-
func kConcatenationMaxSum(arr []int, k int) int { var s, mxPre, miPre, mxSub int for _, x := range arr { s += x mxPre = max(mxPre, s) miPre = min(miPre, s) mxSub = max(mxSub, s-miPre) } const mod = 1e9 + 7 ans := mxSub if k == 1 { return ans % mod } mxSuf := s - miPre ans = max(ans, mxSuf+mxPre) if s > 0 { ans = max(ans, mxSuf+(k-2)*s+mxPre) } return ans % mod } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }