[C++] Simple DP using Kadane Algo.
\n#define mod 1000000007\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        long int size=arr.size();\n        if(k==1
```\n#define mod 1000000007\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        long int size=arr.size();\n        if(k==1){\n            return maxSum(arr,size);\n        }\n        else{\n            long long sum=0;\n            for(int i=0;i<arr.size();i++){\n                sum=(sum+arr[i]);\n            }\n            long long kSum=maxSum(arr,size*2);\n            if(sum>0){\n                kSum=(kSum+((k-2)*sum));\n            }\n            return kSum%mod;\n        }\n        return 0;\n    }\n    int maxSum(vector<int> arr,int size){\n        long long int totalMax=0;\n        long long int currMax=0;\n        long long int asize=arr.size();\n        \n        for(int i=0;i<size;i++){\n            currMax=(currMax+arr[i%asize]);\n            if(currMax<arr[i%asize]){\n                currMax=arr[i%asize];\n            }\n            if(currMax>totalMax){\n                totalMax=currMax;\n            }\n        }\n        return totalMax % mod;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']