C/C++ Simple Solution to understand in O(n).
\n#define mod 1000000007\ntypedef long long ll;\n\nclass Solution {\n    ll kadane(vector<int>& arr) {\n        ll curr_sum = 0;\n        ll sum_so_far = 0;\n  
```\n#define mod 1000000007\ntypedef long long ll;\n\nclass Solution {\n    ll kadane(vector<int>& arr) {\n        ll curr_sum = 0;\n        ll sum_so_far = 0;\n        for(int i=0; i<arr.size(); i++)\n        {\n            curr_sum += arr[i];\n            if(curr_sum < 0)\n                curr_sum = 0;\n            else if(curr_sum > sum_so_far)\n                sum_so_far = curr_sum;\n            \n        }\n        return sum_so_far%mod;\n    }\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        //if (k==1) means simply do to Kadane\'s Algo and done\n        if(k==1)\n            return kadane(arr);\n        \n        // if (k != 1) that means we have to modify our array\n        ll sum=0;\n        for(int i=0; i<arr.size() ; i++)\n            sum+=arr[i];\n        \n        // Let\'s have a 2 copy of original array.\n        vector<int> newv;\n            for(int i=0; i<2*arr.size(); i++)\n                newv.push_back(arr[i%arr.size()]);\n        \n        if(sum<0)   // if sum if -ve then apply Kadane\'s over new vector\n            return kadane(newv);\n        \n        else        // if sum is +ve means we have to apply Kadane\'s over n*k array\n            return kadane(newv) + (k-2)*sum%mod;\n            //taking Kadane\'s of 2 copy and adding (k-2) times the sum of original array.\n\n\n\n\n    }\n};\n```
[]