fastest, O(N) C++ solution, with explanation, converting O(k*n) in O(N) solution
\nSo we use kadanes algorithm to find for when k = 1, and k = 2, and store answer \nk =2 in a variable called array_for_two.\nNow after a dry run, we observe a 
```\nSo we use kadanes algorithm to find for when k = 1, and k = 2, and store answer \nk =2 in a variable called array_for_two.\nNow after a dry run, we observe a pattern that,\nfor k = 3, ans = array_for_two + totalsum.\nfor k = 4, ans  = array_for_two + 2totalsum.\nfor k = 5 ans = array_for_two + 3totalsum.\n..\n..\nfor k = r, ans = array_for_two + (r-2)totalsum.\nand this was the basic intuition for converting the code from O(K* N)  to O(N).\nJust if you want to understand, i have posted O(k*N) solution too in the comments.\nAnd if you want the solution to be the fastest submission copy the line \n" static const auto x=[](){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); return nullptr; }(); "\nand paste it before the class solution. It increases the speed of input and output of the code and result in 38ms submission, 99 point something fastest.\n```\n\n\n\n```\nint kadanes(vector<int>& arr, int k){\n        int mod=(int)(1e9+7);\n\n        long csum=0, msum=0;\n        int i=0;\n\n        while(k>0){\n            while(i<arr.size()){\n                csum += arr[i];\n\n                if(csum<0) csum=0;\n                msum= max(csum, msum);\n                i++;\n            }\n            i=0;\n            k--;\n        }\n\n        return (int)(msum % mod);\n    }\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        int ans_for_2=0;\n        long mod = (int)(1e9+7);\n\n        long arr_sum = 0;\n        for(int& e:arr)  arr_sum+=e;\n        \n        for(int i=1; i<=2; i++){\n            int sum = kadanes(arr,i);\n\n            if(k==i){\n                return sum;\n            }\n\n            if(i==2){\n                ans_for_2=sum;\n            }\n        }\n\n        if(arr_sum < 0){\n            return (int)(ans_for_2 % mod);\n        }\n\n        int ans = (int)(ans_for_2 + ((k-2) * (arr_sum) % mod));\n\n        return max(ans,0);\n    }\n```
['C', 'Java']