C++ | Faster than 97.56% | 15 lines
The idea is that after 2 iterations, the max sum will only increase by the same amount. i.e. it will increase by X from iteration 2 to 3, and by the same X from
The idea is that after 2 iterations, the max sum will only increase by the same amount. i.e. it will increase by X from iteration 2 to 3, and by the same X from iteration 3 to 4, and so on. Hence we find what this difference is and multiply accordingly.\n\n```\nint kConcatenationMaxSum(vector<int>& arr, int k) {\n        static int MOD = 1000000007;\n        int firstMaxSum = 0;\n        int secondMaxSum = 0;\n        int maxSum = 0;\n        int sum = 0;\n        for (int i = 0; i < 3; i++) {\n            for (int num : arr) {\n                sum = max(0, sum + num % MOD);\n                maxSum = max(maxSum, sum);\n            }\n            if (i == 0) firstMaxSum = maxSum;\n            else if (i == 1) secondMaxSum = maxSum;\n        }\n        long long diff = maxSum - secondMaxSum;\n        return secondMaxSum + ((diff * (k - 2)) % MOD);\n    }\n```
[]