Java Solution [ With Explanation ]
\n\n\nclass Solution {\n    \n\tpublic int kConcatenationMaxSum(int[] arr, int k) {\n        \n        // Method : Using Kedane\'s Algorithm\n        // Main ta
![image](https://assets.leetcode.com/users/images/48140766-b7ba-4b83-95d8-70ff24c9d228_1611565852.2842824.png)\n\n\nclass Solution {\n    \n\tpublic int kConcatenationMaxSum(int[] arr, int k) {\n        \n        // Method : Using Kedane\'s Algorithm\n        // Main task is to find this positive part ( this will be our max sum )\n        \n        /* \n         * Case 1 : sum of array is positive\n         * Ans = (k-2)*sum + Kedanes(2 arrays joined end to end)\n         * Because (k-2)*sum will be a positive part so adding it will def increase our total sum\n         * And Kedanes(2 arrays joined end to end) is used to find the sum when we discard the \n         * negative part from left end of one array, and negative part from right end from another array\n         */\n        \n        /*\n         * Case 2 : sum of array is negative\n         * Ans = Kedanes(2 arrays joined end to end)\n         */\n\n        int MOD = 1_000_000_007;\n\n        if(k == 1) return kedanes(arr, 1);\n        else{\n            \n            long sum = 0;\n            for(int val:arr) sum += val;\n            \n            if(sum>=0) return (int)(((k-2)*sum)%MOD + kedanes(arr, 2)); \n            else return kedanes(arr, 2);\n            \n        }\n        \n    }\n    \n    public int kedanes(int[] nums, int ch) {\n        \n        int MOD = 1_000_000_007;\n        long cmax = 0, omax = 0;\n        if(ch == 1){\n            for(int i=0;i<nums.length;i++){\n                if(cmax<0) cmax = nums[i]; \n                else cmax += nums[i]; \n                omax = Math.max(omax, cmax); \n            }   \n        }else{\n            for(int i=0;i<2*nums.length;i++){\n                int x = (i%nums.length);\n                if(cmax<0) cmax = nums[x]; \n                else cmax += nums[x]; \n                omax = Math.max(omax, cmax); \n            }  \n        }      \n        \n        return (int)(omax%MOD);\n    }\n}\n\n\nRefer [this ](https://leetcode.com/problems/maximum-subarray/discuss/1034276/2-Java-Solutions-With-explanation) for an explanation to kedane\'s algorithm.
[]