<p>Given an integer array <code>arr</code> and an integer <code>k</code>, modify the array by repeating it <code>k</code> times.</p>

<p>For example, if <code>arr = [1, 2]</code> and <code>k = 3 </code>then the modified array will be <code>[1, 2, 1, 2, 1, 2]</code>.</p>

<p>Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be <code>0</code> and its sum in that case is <code>0</code>.</p>

<p>As the answer can be very large, return the answer <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2], k = 3
<strong>Output:</strong> 9
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,-2,1], k = 5
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [-1,-2], k = 7
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= arr[i] &lt;= 10<sup>4</sup></code></li>
</ul>

using namespace std;
class Solution {
public:
    const int MOD = 1e9 + 7;
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        vector<int> maxMinSumArr;
        bool currPos = true;
        if(arr[0] < 0)
                currPos = false;
        long long runningSum = 0;
        long long totalRunningSum = 0;
        for(int i = 0; i < arr.size();i++){
            totalRunningSum += arr[i];
            if(arr[i] < 0 && currPos == true){
                maxMinSumArr.push_back(runningSum);
                runningSum = arr[i];
                currPos = false;
            }
            else if (arr[i] < 0)
                runningSum += arr[i];
            else if (arr[i] > 0 && currPos == false){
                maxMinSumArr.push_back(runningSum);
                runningSum = arr[i];
                currPos = true;
            }
            else if (arr[i] > 0)
                runningSum += arr[i];
        }
        maxMinSumArr.push_back(runningSum);
        long long maximumsArr[4];
        long long currSum = 0;
        long long maxSum = -INT_MAX;
        for(int i = 0 ;i < maxMinSumArr.size();i++){
            currSum += maxMinSumArr[i];
            if(currSum > maxSum)
                maxSum = currSum;
            if(currSum < 0)
                currSum = 0;
        }
        maximumsArr[0] = maxSum;
        maximumsArr[1] = totalRunningSum * k;
        int startIndex = 0;
        if(maxMinSumArr[0] < 0)
            startIndex = 1;
        long long suffixSum = -INT_MAX;
        long long currSuffSum = 0;
        for(int i = maxMinSumArr.size()-1; i >= startIndex;i--) {
            currSuffSum += maxMinSumArr[i];
            if(currSuffSum > suffixSum)
                suffixSum = currSuffSum;
        }
        long long prefixSum = 0;
        long long currPreSum = 0;
        int endIndex = maxMinSumArr.size() -1;
        if(maxMinSumArr[endIndex] < 0)
            endIndex--;
        for(int i = 0; i <= endIndex; i++){
            currPreSum += maxMinSumArr[i];
            if(currPreSum > prefixSum)
                prefixSum = currPreSum;
        }
        if(suffixSum > -INT_MAX && prefixSum > -INT_MAX && k > 1){
            maximumsArr[2] = suffixSum + prefixSum + (k-2)*totalRunningSum;
            maximumsArr[3] = suffixSum + prefixSum;
        }
        long long biggestSubArr = maximumsArr[0];
        if (maximumsArr[1] > biggestSubArr)
            biggestSubArr = maximumsArr[1];
        if (maximumsArr[2] > biggestSubArr)
            biggestSubArr = maximumsArr[2];
        if (maximumsArr[3] > biggestSubArr)
            biggestSubArr = maximumsArr[3];
        return biggestSubArr > 0 ? biggestSubArr % MOD: 0;
/*
        vector<int> copy;
        for(int i = 0; i < maxMinSumArr.size();i++){
            copy.push_back(maxMinSumArr[i]);
        }
        for(int i = 0; i < k-1; i++){
            maxMinSumArr.insert(maxMinSumArr.end(),copy.begin(),copy.end());
        }
        long long maxSum = -INT_MAX;
        long long currSum = 0;
        for(int i = 0; i < maxMinSumArr.size();i++){
            currSum += maxMinSumArr[i];
            if(currSum < 0){
                currSum = 0;
            }
            else if( currSum > maxSum)
                maxSum = currSum;
        }
        return maxSum > 0 ? maxSum % (long long)(MOD) : 0;*/
    }
};
43500