1191

1191. K-Concatenation Maximum Sum (Medium)

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 109 + 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 <= 105
• 1 <= k <= 105
• -104 <= arr[i] <= 104

Related Topics:
Dynamic Programming

Solution 1.

// OJ: https://leetcode.com/problems/k-concatenation-maximum-sum/
// Author: github.com/lzl124631x
// 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;
    }
};

TODO

write explanation