Java Solution faster than 99.21% of Java online submissions
\nclass Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        \n        // Prefix Sum\n        int n=arr.length;\n        long prefix_sum
```\nclass Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        \n        // Prefix Sum\n        int n=arr.length;\n        long prefix_sum=arr[0];\n        long max_prefix_sum=arr[0];\n        for(int x=1;x<n;x++)\n        {\n            prefix_sum+=arr[x];\n            max_prefix_sum=Math.max(max_prefix_sum, prefix_sum);\n        }\n       \n        if(max_prefix_sum <0)\n        {\n            prefix_sum=0;\n        }\n        //Kadens Algorithm\n        long curr_sum=arr[0];\n        long best_sum=arr[0];\n        for(int x=1;x<n;x++)\n        {\n            curr_sum=Math.max(curr_sum+arr[x], arr[x]);\n            best_sum=Math.max(curr_sum, best_sum);\n        }\n        \n        \n        \n      //Suffix_sum\n         long suffix_sum=arr[n-1];\n        long  max_suffix_sum=arr[n-1];\n        for(int x=n-2;x>=0;x--)\n        {\n            suffix_sum+=arr[x];\n            max_suffix_sum=Math.max( max_suffix_sum, suffix_sum);\n        }\n        \n        \n       \n        long kk=(long)prefix_sum*k;\n        long maxs= Math.max(kk, Math.max(best_sum,Math.max( max_suffix_sum+max_prefix_sum*(k==1?0:1),\n                                                               max_suffix_sum+(long)prefix_sum*(k-1))));\n        \n        \n        \n        maxs=Math.max(maxs,prefix_sum*(k-1)+max_prefix_sum);\n              \n\n        maxs=Math.max(maxs, max_suffix_sum+ prefix_sum*(k<=1?0:k-2)+max_prefix_sum*(k==1?0:1));\n               \n\n        return (int)(maxs%1000000007);\n        \n        \n        \n        \n        \n        \n    }\n}\n```
['Java']