Java, T = O(N), S = O(1)
\nclass Solution {\n\n  private static final int MOD = (int) 1e9 + 7;\n\n  // T = O(N), S = O(1)\n  public int kConcatenationMaxSum(int[] arr, int k) {\n    int
```\nclass Solution {\n\n  private static final int MOD = (int) 1e9 + 7;\n\n  // T = O(N), S = O(1)\n  public int kConcatenationMaxSum(int[] arr, int k) {\n    int n = arr.length;\n    long max = getMaxSubSum(arr, n);\n    if (k == 1) return asIntMod(max);\n    max = Math.max(max, getMaxSubSum(arr, n * 2));\n    return asIntMod(Math.max(max, getKConcatMaxSum(arr, k)));\n  }\n\n  private long getMaxSubSum(int[] arr, int n) {\n    long sum = 0, max = 0;\n    for (int i = 0; i < n; i++) {\n      sum += arr[i % arr.length];\n      max = Math.max(max, sum);\n      if (sum < 0) sum = 0;\n    }\n    return max;\n  }\n  \n  private int asIntMod(long num) {\n    return (int) (num % MOD);\n  }\n\n  private long getKConcatMaxSum(int[] arr, int k) {\n    int n = arr.length;\n    long left = 0, right = 0, minLeft = 0, minRight = 0;\n    for (int i = 0; i < n; i++) {\n      left += arr[i];\n      right += arr[n - 1 - i];\n      minLeft = Math.min(minLeft, left);\n      minRight = Math.min(minRight, right);\n    }\n    return (left * k) + -minLeft + -minRight;\n  }\n}\n```
[]