Java Solution(Kadens Algo) with Explanation
Explanation:\n The problem is to find the maximum sub array of concatenatedarr. \n Maximum SubArray of an array A is a continuous SubArray within the array A th
Explanation:\n The problem is to find the maximum sub array of *concatenatedarr*. \n Maximum SubArray of an array A is a continuous SubArray within the array A that has the largest Sum. \n The best method for finding Maximum SubArray is Kadanae\'s algorithm.\n \n Here you have to find the Maximum SubArray for an array concatenated_arr which is a k-times repetitive array of A. For e.g.. if A is {3, 2, -1} and K is 3 then B will be {3, 2, -1, 3, 2, -1, 3, 2, -1}. Method:\nThe maximum SubArray of concatenated_arr can be the sum of all its elements. \nFor e.g.. if A is {3, 2, -1} and K is 3, then B will be {3, 2, -1, 3, 2, -1, 3, 2, -1}. \nThe sum of all the elements in concatenated_arr will give us 12. To find this one we don\'t need to create the array concatenated_arr. \nWe can simply find the sum of all the elements in array A and we can mutilply it with K. \n But wait, we can omit the last term in it so that the sum will become 13. \nFor this one we can use prefix and suffix calculations. \nEg:\n A is repeated k times in *concatenatedarr*. \nConsider the first repetition of A is A1, second is A2 and so on. So now our B array(if K=8) will be {A1, A2, A3, A4, A5, A6, A7, A8}. If you omit the first two elements in A1 and the last two elements in A8, you might also get the maxsub array.\nSo here we can check whether it is possible to omit some initial elements in A1 and some Final elements in A8. We use prefix and suffix variables for that to calculate the sum of A1 and A10 specifically and he adds the remaining elements i.e answer = {prefix + sum_of_elements(A2) + sum_of_elements(A3) + sum_of_elements(A4) + sum_of_elements(A5) + sum_of_elements(A6) + sum_of_elements(A7) + suffix} , which in simplified form becomes {prefix + sum_of_elements(A)*(k-2) + suffix}. \n\n```\n int mod  = (int) Math.pow(10,9)+7;\n    public int kConcatenationMaxSum(int[] ar, int k) {\n        long kadanes= kadanesAlgo(ar);\n        if(k==1){\n            return (int)kadanes;\n        }\n        long prefixSum= prefixSum(ar);\n        long suffixSum=suffixSum(ar);\n        long sum=0;\n        for (int i1 : ar) {\n            sum += i1;\n        }\n        if(sum>0){\n            return (int)(Math.max(((sum*(k-2))%mod+suffixSum%mod+prefixSum%mod)%mod,kadanes%mod));\n        }\n        else{\n            return (int)(Math.max((prefixSum%mod+suffixSum%mod)%mod,kadanes%mod));\n        }\n\n    }\n    public  long kadanesAlgo(int[] ar){\n\n        long currentSum=0;\n        long maxSum=Integer.MIN_VALUE;\n        for(int i=0;i<ar.length;i++){\n            currentSum=currentSum>0?(currentSum+ar[i])%mod:ar[i];\n            maxSum=Math.max(currentSum,maxSum);\n        }\n        return maxSum<0?0:maxSum%mod;\n\n    }\n\n\n    public  long prefixSum(int[] ar){\n\n        long currentSum=0;\n        long maxSum=Integer.MIN_VALUE;\n        for(int i=0;i<ar.length;i++){\n            currentSum= (currentSum+ar[i])%mod;\n            maxSum=Math.max(maxSum,currentSum);\n        }\n        return maxSum;\n\n\n    }\n\n    public  long suffixSum(int[] ar){\n\n\n        long currentSum=0;\n        long maxSum=Integer.MIN_VALUE;\n        for(int i=ar.length-1;i>=0;i--){\n            currentSum=(currentSum+ar[i])%mod;\n            maxSum=Math.max(currentSum,maxSum);\n        }\n        return maxSum;\n\n    }\n```
[]