90% Faster C++ Solution
\nclass Solution {\npublic:\n    #define mod 1000000007\n    int kadaneAlgo(vector<int>& arr)\n    {\n        vector<int> dp(arr.size(),0);\n        int osum = 
```\nclass Solution {\npublic:\n    #define mod 1000000007\n    int kadaneAlgo(vector<int>& arr)\n    {\n        vector<int> dp(arr.size(),0);\n        int osum = arr[0];\n        int csum = arr[0];\n        dp[0] = arr[0];\n        for(int i=1;i<arr.size();i++)\n        {\n            if(csum+arr[i] < arr[i])\n            {\n                csum = arr[i];\n            }else{\n                csum = (csum+arr[i])%mod;\n            }\n            \n            if(osum < csum)\n            {\n                osum = csum;\n            }\n        }\n        if(osum < 0)\n            return 0;\n        return osum;\n    }\n    \n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        if(k == 1)\n            return kadaneAlgo(arr);\n        int sum = 0;\n        bool isNegative = false;\n        for(int i=0;i<arr.size();i++)\n        {\n            if(arr[i] < 0)\n                isNegative = true;\n            sum = (sum+arr[i])%mod;\n        }\n        \n        if(isNegative == false)\n        {\n            return (long)sum*k%mod;\n        }\n        \n        vector<int> arr2(arr.size()*2);\n        for(int i=0;i<arr2.size();i++)\n        {\n            arr2[i] = arr[i%arr.size()];\n        }\n        if(sum < 0)\n        {\n            return kadaneAlgo(arr2);\n        }\n        \n        \n        \n        return (kadaneAlgo(arr2)+(long)(k-2)*sum)%mod;\n    }\n};\n```
['C', 'C++']