Java : Discussion of Cases
java\nclass Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        \n        /*\n        If k = 1, the problem is not hard to solve in O(N
```java\nclass Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        \n        /*\n        If k = 1, the problem is not hard to solve in O(N) time O(1) space with Kadane Algorithm\n       \n        Considering the cases for k > 1:\n        \n        1) If the sum of arr < 0:\n        1.1) If all the elements are negative, return 0;\n        1.2) Kadane algorithm result for k=1\n        1.3) max(max_prefix_sum, 0) + max(max_suffix_sum, 0)\n        \n        2) If the sum of arr >= 0:\n        2.1) And the first and last elem > 0, the result is sum(arr) * k\n        2.2) But eitehr the first or last elem is negative, \n        thus we have to exclude those margin elements, e.g. [-1,4,-2] k=3, \n        we should remove -1 from the begininng and -2 from the end of [-1,4,-2,-1,4,-2,-1,4,-2]. \n        So it is (k-2) * sum(arr) + max_prefix_sum + max_suffix_sum\n        */\n        \n        int mod = (int) 1e9 + 7;\n        \n        int n = arr.length;\n\t\tlong maxsub = arr[0], cursub = arr[0]; // subarray sum\n        long maxpre = arr[0], curpre = arr[0]; // prefix sum\n        long maxsuf = arr[n-1], cursuf = arr[n-1]; // suffix sum\n        \n        for (int i = 1; i < n; i++) {\n            if (cursub > 0) cursub = arr[i] + cursub;\n            else cursub = arr[i]; \n            maxsub = Math.max(cursub, maxsub); // Kadane algorithm with O(1) space\n\t\t\tcurpre += arr[i];\n            maxpre = Math.max(maxpre, curpre);\n        }\n        \n        for (int i = n-2; i >= 0; i--) {\n            cursuf += arr[i];\n            maxsuf = Math.max(maxsuf, cursuf);\n        }\n        \n        if (k == 1) return (int) (maxsub % mod);\n        else if (maxsub < 0) return 0;  // all elements are negative\n        \n        else {\n            long sums = curpre;\n            long res1 = sums * k;\n            long res2 = Math.max(0, sums * (k-2)) + Math.max(0, maxpre) + Math.max(0, maxsuf); // combine case 1.3) and 2.2)\n            long res3 = maxsub;\n            \n            return (int) (Math.max(res1, Math.max(res2, res3)) % mod);\n        } \n    }\n}\n```
[]