O(N) easy C++ solution
Intuition\nWhen the arr\'s sum is positive, consider k. When k > 2, use Kadane\'s algorithm to calculate maximum subarray of 2 arrs(one in the front and one at 
# Intuition\nWhen the arr\'s sum is positive, consider k. When k > 2, use Kadane\'s algorithm to calculate maximum subarray of 2 arrs(one in the front and one at the end) and add the sum of all the middle arrs.\nWhen the arr\'s sum is negative, we only need to use Kadane\'s algorithm to calculate the maximum subarray of 2 arrs.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nclass Solution {\n    int M=1000000007;\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        int sum=0;\n        long long int res=0;\n        vector<int> arr2(arr);\n        arr2.insert(arr2.end(),arr.begin(),arr.end());\n        if(k==1) return largest(arr)%M;\n        if(k==2) return largest(arr2)%M;\n        for(int i:arr) sum+=i;\n        if(sum>0)\n        {\n            res=(long long int)(k-2)*sum%M;\n            res=(res+largest(arr2))%M;\n        }\n        else\n        {\n            res=largest(arr2)%M;\n        }\n        return res;\n    }\n\n    int largest(vector<int>& arr)\n    {\n        int best_sum = 0;\n        int current_sum = 0;\n        for (int x:arr)\n        {\n            current_sum = max(0, current_sum + x);\n            best_sum = max(best_sum, current_sum);\n        }\n        return best_sum;      \n    }\n};\n```
['C++']