using java kadanes algo
\n    class Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        List l=new ArrayList<>();\n        long mod=(long)(1e9)+7;\n       long
\n    class Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        List<Integer> l=new ArrayList<>();\n        long mod=(long)(1e9)+7;\n       long sum=0;\n        for(int x:arr){\n            sum+=(long)x;\n            l.add(x);\n        }\n        //condition for k==1\n         if(k==1){\n            long z=kadanes(l);\n            return (int)(z%mod);\n        }\n        //if sum is neg applying two times kadanes\n        else if(sum<0){\n            for(int x:arr)l.add(x);\n            long z=kadanes(l);\n            return (int)(z%mod);\n        }\n        //if sum is pos applying two times kadanes and adding the k-2 times whole sum\n        else{\n            for(int x:arr)l.add(x);\n            long z=kadanes(l);\n            long p1=z+(k-2)*sum;\n            return (int)(p1%mod);\n        }\n            \n    }\n    //kadanes algo\n    public long kadanes(List<Integer> l){\n        long prev=0;long max=0;\n        for(int i=0;i<l.size();i++){\n            prev=Math.max(prev+(long)l.get(i),(long)l.get(i));\n            max=Math.max(max,prev);\n        }\n        return max;\n    }\n}
[]