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
}

All Problems

All Solutions