1191. K-Concatenation Maximum Sum

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.

c++

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long long totalSum = 0;
        long long answer = 0;
        long long maxValue = 0;
        long long minValue = 0;
        for(int i = 0; i < arr.size(); i++) {
            totalSum += arr[i];
            maxValue = max(maxValue, totalSum);
            minValue = min(minValue, totalSum);

            answer = max(answer, totalSum - minValue);
        }

        if(k > 1) {
            answer = max(answer, max(totalSum - minValue + maxValue, totalSum * (k - 1) + max(totalSum - minValue, maxValue)));
            
            if(k > 2) {
                answer = max(answer, totalSum * (k - 2) + totalSum - minValue + maxValue);
            }
        }

        return max(totalSum * k, answer) % 1000000007;
    }
};