Kadane Algorithm (Golang)
Complexity\n- Time complexity: O(n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(1)\n Add your space complexity here, e.g. O(n) \n\n# Co
# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfunc kConcatenationMaxSum(arr []int, k int) int {\n    var mod int = 1e9 + 7\n    var n int = len(arr)\n\n    if k == 1 {\n        return MaxSubArr(arr, n, 1) % mod\n    }\n\n    sum := Sum(arr, n)\n\n    if sum <= 0 {\n        return MaxSubArr(arr, n, 2) % mod\n    }\n\n    ans := MaxSubArr(arr, n, 2)\n\n    return (ans + (k - 2) * sum) % mod\n}\n\nfunc max(a, b int) int {\n    if a > b { return a }\n    return b\n}\n\nfunc MaxSubArr(arr []int, n int, k int) int {\n    sum := 0\n    ans := 0\n\n    for i := 0; i < n * k; i++ {\n        sum = max(sum + arr[i % n], 0)\n        ans = max(sum, ans)\n    }\n\n    return ans\n}\n\nfunc Sum(arr []int, n int) int {\n    sum := 0\n\n    for i := 0; i < n; i++ {\n        sum += arr[i]\n    }\n\n    return sum\n}\n```
['Go']