Complete explaination of short and precise code | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first though that come\'s to mind while solving this problem is to: \n1. Find naxim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first though that come\'s to mind while solving this problem is to: \n1. Find naximum sum using Kadane\'s algorithm.\n2. Find the maximum prefix and suffix sum and then add them to $$(k - 2) * total$$ where $$total$$ is the total sum of the array. \n3. Return the maximum from both the above answers.\n\nBut here\'s the catch, we don\'t need to solve for both the sums separately. We will directly take the given array twicw when $$k >= 2$$ and apply Kadane\'s to it, add $$(k - 2) * total$$ to the answer returned from Kadane\'s algorithm. Note the sum returned can be of the subarray which contains intersection(made from prefix and suffix sum) and also which doesn\'t. But we are adding $$(k - 2) * total$$ irrespective of whether it contains the intersection or not.\n\nLet\'s prove why this work\'s:\nTake an array $$A = [a, b, c]$$. $$a$$ represents the prefix of the array, $$b$$ represents the subarray from which we got the maximum sum using Kadane\'s algorithm and $$c$$ represents the suffix of the array. If $$(k >= 2)$$, the array would look like $$A1 = [a, b, c, a, b, c]$$ if we take the array twice. Few things to note here:\n1. $$a + c$$ should be negative, if not, then we had added it to $$b$$ to make maximum subarray.\n2. $$b$$ should be positive, in the case where $$b$$ is negative, answer would be 0, because then the whole array is negative.\n\nNow we have 2 cases:\n1. $$b > |a + c|$$, sum of whole array is positive.\n2. $$b < |a + c|$$, sum of whole array is negative\n\nIn the first case, we have $$b + a + c > 0$$, since $$b$$ is greater than $$|a + c|$$. If we will add $$b$$ to both the sides of the equation, we will get $$b + a + c + b > b$$. Hence this proves that $$prefix + suffix$$ will always have a sum greater then that we got using Kadane\'s algorithm on the $$A$$ array i.e. $$b$$(note that $$b + a + c + b$$ contains intersection). This proves theat if we combine the array twice and then use Kadane\'s algorithm, the subarray will always lie of the intersection of the two arrays. Hence we can use Kadane\'s on the $$A1$$ array, it will give $$b + a + c + b$$ as the maximum subarray and then we will just add this to $$(k - 2) * total$$ which will only increase that answer since the sum of whole array is positive.\n\nIn the second case, since the sum of whole array is negative and hence we don\'t need to take care of $$prefix-suffix$$ sum to multiply it by $$(k - 2) * total$$ because $$total$$ is negative and it will only make the sum less. Hence, whatever Kadane\'s return will be the answer.\n\nHence we have proved that we do not need to calculate the two sum\'s separately.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        int curr_max = 0, ans = 0;\n        int n = arr.size();\n        int total_sum = 0;\n        for (int i = 0; i < n * min(k, 2); i++) {\n            curr_max = max(curr_max + arr[i % n], arr[i % n]);\n            ans = max(ans, curr_max);\n            total_sum += arr[i % n];\n        }\n        total_sum /= 2;\n        int MOD = 1e9 + 7;\n        int sumk = (k > 1 ? ((long)(k - 2) * total_sum) % MOD : 0);\n        return max(ans % MOD, (ans + sumk) % MOD);\n    }\n};\n```
['C++']