C++ Dynamic Programming O(n) Time
Dynamic Programming, Greedy \n\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        if(k==1){\n            return calMax
Dynamic Programming, Greedy \n```\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        if(k==1){\n            return calMaxSum(arr, 1)%1000000007;\n        }else{\n            int max_sum=calMaxSum( arr, 2)%1000000007, \n                tot=calSum( arr );\n            if(0<tot)\n                return max_sum+(long long)tot*(k-2)%1000000007;\n            else\n                return max_sum;\n        }\n    }\n    \nprotected:\n    int calMaxSum( vector<int> & arr, int repeat){\n        long long max_sum=0, pre_sum=0;// max of sum of subarray ending at i\n        for( int j=0; j<repeat; j++){\n            for( int i=0; i<arr.size(); i++){\n                pre_sum+=arr[i];\n                if(0<arr[i]){\n                    if(max_sum<pre_sum)\n                        max_sum=pre_sum;\n                }else{\n                    if(pre_sum<0)\n                        pre_sum=0;\n                }\n            }\n        }\n        return max_sum%1000000007;\n    }\n    \n    int calSum(vector<int> & arr){\n        long sum=0;\n        for( int i=0; i<arr.size(); i++)\n            sum=(sum+arr[i])%1000000007;\n        return sum;\n    }\n};\n```
[]