C++ O(n) Explained
``` \n#define m 1000000007\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector& ar, int k) {\n        long long int ans = INT_MIN;\n\t    long long 
``` \n#define m 1000000007\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& ar, int k) {\n        long long int ans = INT_MIN;\n\t    long long int sum = 0;\n        int n = ar.size();\n        \n        // kadane\'s for max sum subarray\n        for(int j=0 ; j<n ; j++){\n            ans = max((int)ans, ar[j]);\n            sum = (sum + ar[j]) % m ;\n            ans = max(ans, sum);\n            if(sum < 0)\n                sum = 0;\n        }\n        if(k == 1)\n            return ans % m;\n        \n        // total intermediate sum\n        sum = 0;\n        for(auto n : ar)\n            sum = (sum + n) % m;\n        \n        // subarray sum from end\n        int a = 0;\n        int send = 0;\n        for(int i=n-1 ; i>=0 ; i--) {\n            a = (a + ar[i]) % m;\n            send = max(send, a);\n        }\n\n        // subarray sum from front\n        int b = 0;\n        int sbegin = 0;\n        for(int i=0 ; i<n ; i++){\n            b = ((b + ar[i])) % m;\n            sbegin = max(sbegin, b);\n        }\n        \n        if(sum >= 0){\n            sum = (sum%m * (k-2)%m) % m;\n            if(sbegin >= 0)\n                sum = (sum + sbegin) % m;\n            if(send >= 0)\n                sum = (sum + send) % m;\n        }\n        else\n            sum = max( (send + sbegin)%m , max(send, sbegin) );\n            \n        return max(ans,sum);\n    }\n};\n````
['C', 'C++']