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 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

If k = 1, find the maximum sub-array sum in arr.

Else if k = 2 or sum(arr) <= 0, find the maximum sub-array sum in concat(arr, arr). (The maximum sub-array cannot contain a complete arr if sum(arr) <= 0)

Else find the maximum sub-array sum in concat(arr, arr) + sum(arr) * (k - 2).

Let max_sum[i] be maximum sub-array sum ending with arr[i]. Then,

\text{max_sum[i]} = \text{sum}(\text{arr}[0..i]) - \min_{j \le i} \text{sum}(\text{arr}[0..i])

Or \text{max_sum}[i] = \max(\text{arr}[i], \text{max_sum}[i-1] + \text{arr}[i]).

Solution 1

#define MOD (1'000'000'000 + 7)

class Solution {
public:
    int kConcatenationMaxSum(vector<int> &arr, int k) {
        long total_sum, min_sum, max_sum;
        total_sum = min_sum = max_sum = 0;
        for (int i = 0; i < arr.size(); ++i) {
            total_sum += arr[i];
            min_sum = min(total_sum, min_sum);
            max_sum = max(total_sum - min_sum, max_sum);
        }
        if (k == 1 || max_sum == 0)
            return max_sum;
        long onepass_sum = total_sum;
        for (int i = 0; i < arr.size(); ++i) {
            total_sum += arr[i];
            min_sum = min(total_sum, min_sum);
            max_sum = max(total_sum - min_sum, max_sum);
        }
        if (k == 2 || onepass_sum < 0)
            return max_sum % MOD;
        return (max_sum + (k - 2) * onepass_sum) % MOD;
    }
};

Solution 2

#define MOD (1'000'000'000 + 7)

class Solution {
public:
    int kConcatenationMaxSum(vector<int> &arr, int k) {
        int64_t total = accumulate(arr.begin(), arr.end(), 0);
        int sum = 0, max_sum = 0, n = arr.size();
        for (int i = 0; i < n * min(k, 2); ++i) {
            sum = max(arr[i % n], sum + arr[i % n]); // sum: maximum subarray sum ending with arr[i]
            max_sum = max(sum, max_sum);             // max_sum: maximum subarray sum in arr[0..i]
        }
        if (k <= 2 || total <= 0)
            return max_sum % MOD;
        return (max_sum + (k - 2) * total) % MOD;
    }
};