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

Solution: (Kadane's Algorithm)

Approach:

• Case 1: (k = 1)

  Use Kadane's algo

• Case 2: (sum > 0)

  s1 + s2 + s3 + s4

  suffix of s1 + (k-2) * s + prefix + s4

  Kadanes (first two array) * (k-2) * s

• Case 3: (sum < 0)

  Kadanes (first two array)

class Solution
{
public:
    long long int findMax(vector<int> &arr)
    {
        int m = 1000000007;
        int s = 0;
        int maxSum = 0;

        for (int i = 0; i < arr.size(); i++)
        {
            s = s + arr[i];

            maxSum = max(maxSum, s);

            if (s < 0)
            {
                s = 0;
            }
        }
        return maxSum;
    }

    int kConcatenationMaxSum(vector<int> &arr, int k)
    {

        int n = arr.size();
        int m = 1000000007;

        int maxSum = findMax(arr);

        vector<int> v(2 * n);

        for (int i = 0; i < 2 * n; i++)
        {
            v[i] = arr[i % n];
        }

        int maxSumMerged = findMax(v);

        long long s = 0;

        for (int i = 0; i < n; i++)
        {
            s = s + arr[i];
        }

        if (k == 1)
        {
            return maxSum;
        }

        if (s < 0)
        {
            return maxSumMerged;
        }

        int ans = (maxSumMerged + ((k - 2) * (s))) % m;
        return ans;
    }
};

Time Complexity:O(n)