K-Concatenation Maximum Sum

Jin Shang bio photo By Jin Shang

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:

Two possible options:

1) Max sum in the array itself

2) Right most + Left most + (k-2)*sum if sum > 0 (prefix sum)

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long long ans1 = 0;
        long long cur = 0;
        for(int i = 0; i < arr.size(); i++){
            cur += arr[i];
            if(cur < 0){
                cur = 0;
            }
            ans1 = max(ans1, cur);
        }
        
        long long l = 0, r = 0;
        vector<long long> sum(arr.size()+1, 0);
        for(int i = 0;i < arr.size(); i++){
            sum[i+1] = sum[i]+arr[i];
        }
        
        for(int i = 0;i <arr.size(); i++){
            l = max(l, sum[i+1]);
            r = max(r, sum[arr.size()] - sum[i]);
        }
        cout<<l<<" "<<r<<" "<<sum[arr.size()]<<"\n";
        long long ans2 = l+r;
        if(sum[arr.size()]>0 && k>2) ans2 += (k-2)*sum[arr.size()];
        
        long long ans = max(ans1,ans2);
        
        return ans % (1000000007LL);
    }
};