K-Concatenation Maximum Sum | Java | Easy | Kadane's Algorithm
\nclass Solution {\n    int mod=1000000007;\n    \n    public int kConcatenationMaxSum(int[] arr, int k) {\n        if(k==1){\n            return kadane(arr);\n
```\nclass Solution {\n    int mod=1000000007;\n    \n    public int kConcatenationMaxSum(int[] arr, int k) {\n        if(k==1){\n            return kadane(arr);\n        }else{\n            long sum=0;\n            for(int i=0;i<arr.length;i++){\n                sum+=arr[i];\n            }\n            \n            if(sum<0){\n                int val= merge(arr);\n                if(val<0){\n                    return 0;\n                }else{\n                    return val;\n                }\n            }else{\n                int val=merge(arr);\n                return (int)(val+((k-2)*sum)%mod)%mod;\n            }\n        }\n    }\n    \n    public int kadane(int []arr){\n        long localMax=arr[0];\n        long globalMax=arr[0];\n        \n        for(int i=1;i<arr.length;i++){\n            localMax+=arr[i]%mod;\n            localMax=Math.max(localMax,arr[i]);\n            globalMax=Math.max(globalMax,localMax);\n        }\n        \n        return (int)globalMax;\n    }\n    \n    public int merge(int []arr){\n        int n=arr.length;\n        int []nums=new int[n+n];\n        \n        \n        for(int i=0;i<n;i++){\n            nums[i]=arr[i];\n        }\n        \n        for(int i=0;i<n;i++){\n            nums[n+i]=arr[i];\n        }\n        \n       \n        return kadane(nums);\n    }\n}\n```
['Java']