[Python] Solution faster than 99.6%
\nclass Solution:\n    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n        if (k == 1):\n            return self.ConcatenationMaxSum(arr) % 
```\nclass Solution:\n    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:\n        if (k == 1):\n            return self.ConcatenationMaxSum(arr) % (10**9 + 7)\n        \n        sum_ = sum(arr)\n        arr2_ans = self.ConcatenationMaxSum(arr * 2) % (10**9 + 7)\n        if sum_ > 0:\n            return (arr2_ans + (sum_ * (k-2))) % (10**9 + 7)\n        else :\n            return arr2_ans\n\n    \n    def ConcatenationMaxSum(self, arr: List[int]) -> int:#sum, start, end\n        s, s_tmp = 0, 0\n        phase = True\n        for i, x in enumerate(arr):\n            s_tmp += x\n            if (s_tmp < 0):\n                s_tmp = 0\n            \n            if (phase):\n                if (x >= 0):\n                    s += x\n                else:\n                    phase = False\n                    \n            elif (s_tmp > s):\n                s = s_tmp\n                phase = True\n        \n        return s\n```
['Python', 'Python3']