Easy to understand O(N) C++ Solution
\nclass Solution {\npublic:\n    typedef long long ll;\n    ll p=1e9+7;\n    int kadane(vector<int> v) {\n        int n=v.size();\n        vector<ll> dp(n);\n  
```\nclass Solution {\npublic:\n    typedef long long ll;\n    ll p=1e9+7;\n    int kadane(vector<int> v) {\n        int n=v.size();\n        vector<ll> dp(n);\n        dp[0]=max(0,v[0]);\n        ll ans=dp[0];\n        for(int i=1;i<n;i++) {\n            dp[i]=max((ll)0,max((ll)v[i],(ll)v[i]+dp[i-1]));\n            ans=max(ans,dp[i]); \n        }\n        return max(ans,(ll)0)%p;\n    }\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        ll s=0; int n=arr.size();\n        for(auto x: arr) { s+=x; }\n        if(k==1) {\n            return kadane(arr)%p;\n        }\n        else if(s<0) {\n            vector<int> v(2*n);\n            for(int i=0;i<n;i++) v[i]=arr[i];\n            for(int i=0;i<n;i++) v[i+n]=arr[i];\n            return kadane(v)%p;\n        }\n        else {\n            ll ans=(k-2)*s; ans%=p;\n            vector<int> v(2*n);\n            for(int i=0;i<n;i++) v[i]=arr[i];\n            for(int i=0;i<n;i++) v[i+n]=arr[i];\n            ans+=kadane(v)%p;\n            return ans%p;\n        }\n        return 0;\n    }\n};``\n```
['Dynamic Programming', 'C', 'C++']