Skip to content

1191. K-Concatenation Maximum Sum

SourceWeekly Contest 154 Q3DifficultyMediumRating1747

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 109 + 7.

 

Example 1:

Input: arr = [1, 2], k = 3

Output: 9

Explanation:

The concatenated array is [1, 2, 1, 2, 1, 2].

The maximum-sum subarray is the entire array, with sum 1 + 2 + 1 + 2 + 1 + 2 = 9.

Example 2:

Input: arr = [1, -2, 1], k = 5

Output: 2

Explanation:

The concatenated array is [1, -2, 1, 1, -2, 1, 1, -2, 1, 1, -2, 1, 1, -2, 1].

The maximum-sum subarray is [1, 1], formed by the last element of one copy and the first element of the next copy, with sum 1 + 1 = 2.

Example 3:

Input: arr = [-1, -2], k = 7

Output: 0

Explanation:

Every element in the concatenated array is negative, so no subarray has a positive sum. Therefore, the maximum possible sum is 0.

 

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= k <= 105
  • -104 <= arr[i] <= 104

Solutions

Solution 1: Prefix Sum + Case Discussion

Thinking

After repeating \(\textit{arr}\) \(k\) times, an optimal subarray spans at most the whole concatenation. Kadane on one copy gives \(\textit{mxSub}\), plus the max prefix and min prefix (hence max suffix). For \(k=1\) that is the answer; otherwise also consider prefix+suffix, and if the total is positive add \(k-2\) full copies. \(k\) can be \(10^5\), so we never materialize the concatenation.

We denote the sum of all elements in the array \(\textit{arr}\) as \(s\), the maximum prefix sum as \(\textit{mxPre}\), the minimum prefix sum as \(\textit{miPre}\), and the maximum subarray sum as \(\textit{mxSub}\).

We traverse the array \(\textit{arr}\). For each element \(x\), we update \(s = s + x\), \(\textit{mxPre} = \max(\textit{mxPre}, s)\), \(\textit{miPre} = \min(\textit{miPre}, s)\), \(\textit{mxSub} = \max(\textit{mxSub}, s - \textit{miPre})\).

Next, we consider the value of \(k\):

  • When \(k = 1\), the answer is \(\textit{mxSub}\).
  • When \(k \ge 2\), if the maximum subarray spans two \(\textit{arr}\), then the answer is \(\textit{mxPre} + \textit{mxSuf}\), where \(\textit{mxSuf} = s - \textit{miPre}\).
  • When \(k \ge 2\) and \(s > 0\), if the maximum subarray spans three \(\textit{arr}\), then the answer is \((k - 2) \times s + \textit{mxPre} + \textit{mxSuf}\).

Finally, we return the result of the answer modulo \(10^9 + 7\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{arr}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def kConcatenationMaxSum(self, arr: list[int], k: int) -> int:
        s = mx_pre = mi_pre = mx_sub = 0
        for x in arr:
            s += x
            mx_pre = max(mx_pre, s)
            mi_pre = min(mi_pre, s)
            mx_sub = max(mx_sub, s - mi_pre)
        ans = mx_sub
        mod = 10**9 + 7
        if k == 1:
            return ans % mod
        mx_suf = s - mi_pre
        ans = max(ans, mx_pre + mx_suf)
        if s > 0:
            ans = max(ans, (k - 2) * s + mx_pre + mx_suf)
        return ans % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
        for (int x : arr) {
            s += x;
            mxPre = Math.max(mxPre, s);
            miPre = Math.min(miPre, s);
            mxSub = Math.max(mxSub, s - miPre);
        }
        long ans = mxSub;
        final int mod = (int) 1e9 + 7;
        if (k == 1) {
            return (int) (ans % mod);
        }
        long mxSuf = s - miPre;
        ans = Math.max(ans, mxPre + mxSuf);
        if (s > 0) {
            ans = Math.max(ans, (k - 2) * s + mxPre + mxSuf);
        }
        return (int) (ans % mod);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
        for (int x : arr) {
            s += x;
            mxPre = max(mxPre, s);
            miPre = min(miPre, s);
            mxSub = max(mxSub, s - miPre);
        }
        long ans = mxSub;
        const int mod = 1e9 + 7;
        if (k == 1) {
            return ans % mod;
        }
        long mxSuf = s - miPre;
        ans = max(ans, mxPre + mxSuf);
        if (s > 0) {
            ans = max(ans, mxPre + (k - 2) * s + mxSuf);
        }
        return ans % mod;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

Comments