Skip to content

1191. K-Concatenation Maximum Sum

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

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

Solutions

Solution 1: Prefix Sum + Case Discussion

Thinking

After repeating \(arr\) \(k\) times, an optimal subarray spans at most the whole concatenation. Kadane on one copy gives \(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 \(arr\) as \(s\), the maximum prefix sum as \(mxPre\), the minimum prefix sum as \(miPre\), and the maximum subarray sum as \(mxSub\).

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

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

  • When \(k = 1\), the answer is \(mxSub\).
  • When \(k \ge 2\), if the maximum subarray spans two \(arr\), then the answer is \(mxPre + mxSuf\), where \(mxSuf = s - miPre\).
  • When \(k \ge 2\) and \(s > 0\), if the maximum subarray spans three \(arr\), then the answer is \((k - 2) \times s + mxPre + 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)\). Here, \(n\) is the length of the array \(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