1299. K-Concatenation Maximum Sum

• Difficulty: Medium

• Topics: Dynamic Programming

• Similar Questions:

Problem:

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

Solutions:

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        if (k == 0) {
            return maxSubArray(arr);
        } else {
            int sum = 0;
            for (auto& val : arr) {
                sum += val;
            }

            long ret = 0;
            if (sum >= 0) {
                ret += (sum * (long (k - 2))) % MOD;
            }

            arr.insert(arr.end(), arr.begin(), arr.end());
            ret = (ret + maxSubArray(arr)) % MOD;
            return ret;
        }
    }

private:
    int maxSubArray(vector<int>& arr) {
        int sum = 0;
        int ret = 0;
        for (int i = 0; i < arr.size(); ++i) {
            sum += arr[i];
            if (sum < 0) {
                sum = 0;
            } else {
                ret = max(ret, sum);
            }
        }

        return ret;
    }

    int MOD = 1e9 + 7;
};