C++ Clean Solution with Explanation
For K = 1, Answer will be same as Kadanes\n2. For K >= 2, we calculate Kadanes for array + array, i.e, array concatinated once in array.\n3. Imagine the answer 
1. For K = 1, Answer will be same as Kadanes\n2. For K >= 2, we calculate Kadanes for array + array, i.e, array concatinated once in array.\n3. Imagine the answer on kadanes on array(1st array)+array(kth array) as two ends of the actual answer. Now if Sum of the array is greater than 0, we can add (k-2)*(sum) in the answer. Otherwise the answer will be same as Kadanes for array + array.\n```\nclass Solution {\npublic:\n    int kadanes(vector<int> arr, int k){\n        if(k==2){\n            vector<int> v = arr;\n            v.insert(v.end(), arr.begin(), arr.end());\n            arr = v;\n        }\n        int curr_max = 0, ans = 0;\n        for(auto i: arr){\n            curr_max = max(curr_max + i, i);\n            ans = max(ans, curr_max);\n        }\n        return ans;\n    }\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        int mod = 1e9 + 7;\n        if(k==1){\n            return kadanes(arr, 1);\n        }\n        int sum = 0;\n        for(auto i: arr) sum += i;\n        int kn2 = (1ll*(sum%mod)*((k-2)%mod))%mod;\n        int k2 = kadanes(arr, 2)%mod;\n        int ans = max(k2, (k2+kn2)%mod);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']