K-Concatenation Maximum Sum

'''
Logic:
case 1: if k==1,then maximum sum subarray will be answer.
case 2: if sum<0 then answer will be extracted by two array only because if sum<0 for whole then why will
        you take whole array in sum.so answer will be maximum sum subarray of two array  which will be
        partial sum of two array definitely.
case 3: if sum>0 then find maxium sum of two array and sum of rest array*k-2 because 2 array you alread used
        so only k-2 array left.
for eg. [-1,6,-4], k=3  then 6 is the maximum sum subarray.
-1,6,-4,-1,6,-4,-1,6,-4 maxium sum subarray of two combined array is [6,-4,-1,6] ie.7
so we are including elements of second array after the 6 if we have to combine with the third array but in answer , [6,-4,-1,6,-4,-1,6] we compensate it by leaving the same elements of last array.

Even if the maximum sum of two array is including some last elements of the arr and some initial elements of the second array then also we will take the best suffix of first array then the k-1 array sum then the best prefix of the last array.

The maximum subarray sum can't be in between if the total sum of each array is positive arr = [-10, -10, 100, 100, -10], k=3 here total sum of a subarray is 170>0 and max subarray is [100,100] but two of them extended will be having max subarray as [100,100,-10,-10,-10,100,100]=370 so this will autoamtically come in case 3.
'''
from typing import List

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        MOD = 10**9 + 7

        #handle k == 1 first because making arr to arr+arr will miss this case.
        if k == 1:
            cur = 0
            ans = 0
            for num in arr:
                cur += num
                ans = max(ans, cur)
                if cur < 0:
                    cur = 0
            return ans % MOD

        total = sum(arr)
        arr2 = arr * 2

        # kadane on arr + arr
        cur = 0
        ans = 0
        for num in arr2:
            cur += num
            ans = max(ans, cur)
            if cur < 0:
                cur = 0

        if total > 0:
            return (ans + (k - 2) * total) % MOD
        else:
            return ans % MOD