Java time complexity O(N)
The six situations of the maximum-Sum are shown as follows:\n\nSo, in the single array (the array before K-Concatenating), we need to calcaluate these values ar
The six situations of the maximum-Sum are shown as follows:\n![image](https://assets.leetcode.com/users/images/7edc66a7-7a6c-4043-9dbe-58b08c72e2b5_1601443455.1286414.png)\nSo, in the single array (the array before K-Concatenating), we need to calcaluate these values are listed as follow:\n1) sum: the sum of the array\n2) max: the maximum sum of single sub-array\n3) Lmin:  the minimum sum of consecutive sub-arrays starting from the left end\n4) Rmin:  the minimum sum of consecutive sub-arrays starting from the right end\n\nAfter calculating the above four values, the sum of the largest sub-array after K concatenation can be calculated according to the above six situations\n```\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        long sum = 0;\n        for(int i=0;i<arr.length;i++){\n            sum += arr[i];\n        }\n        //======================\n        long max = 0;\n        int slow = 0;\n        int fast = 0;\n        long curSum = 0;\n        while(fast<arr.length){\n            curSum+=arr[fast];\n            if(curSum>max){\n                max = curSum;\n            }\n            while(curSum<0&&slow<=fast){\n                curSum -= arr[slow];\n                slow++;\n            }\n            fast++;\n        }\n        if(curSum>max){\n            max = curSum;\n        }\n        //=====================\n        long min = 0;\n        slow = 0;\n        fast = 0;\n        curSum = 0;\n        while(fast<arr.length){\n            curSum+=arr[fast];\n            if(curSum<min){\n                min = curSum;\n            }\n            while(curSum>0&&slow<=fast){\n                curSum -= arr[slow];\n                slow++;\n            }\n            fast++;\n        }\n        if(curSum<min){\n            min = curSum;\n        }\n        //===============================\n        long leftMin = 0;\n        long rightMax = 0;\n        curSum = 0;\n        for(int i=0;i<arr.length;i++){\n            curSum += arr[i];\n            if(curSum< leftMin){\n                leftMin = curSum;\n            }\n            if(curSum>rightMax){\n                rightMax = curSum;\n            }\n        }\n        //==============================\n        long rightMin = 0;\n        long leftMax = 0;\n        curSum = 0;\n        for(int i=arr.length-1;i>=0;i--){\n            curSum+=arr[i];\n            if(curSum<rightMin){\n                rightMin = curSum;\n            }\n            if(curSum>leftMax){\n                leftMax = curSum;\n            }\n        }\n        //===============================\n        leftMax = Math.max(leftMax, sum-leftMin);\n        rightMax = Math.max(rightMax, sum-rightMin);\n        max = Math.max(max, sum-min);\n        max = Math.max(max, sum*k);\n        max = Math.max(max, (sum*(k-2))+leftMax+rightMax);\n        max = Math.max(max, (sum*(k-1))+leftMax);\n        max = Math.max(max, (sum*(k-1))+rightMax);\n        return (int)(max%(1000000007));\n    }\n```
[]