✅✅Beats 100%✅Fully Explained✅No DP✅✅
Here\u2019s how you can fill out the explanation for your solution:\n\n---\n\n# Intuition\nThe problem asks to find the maximum sum of a subarray for an array r
Here\u2019s how you can fill out the explanation for your solution:\n\n---\n\n# Intuition\nThe problem asks to find the maximum sum of a subarray for an array repeated `k` times. If `k = 1`, we need to find the maximum subarray sum of the original array. For `k > 1`, we can leverage the circular nature of the problem by concatenating the array, as some subarrays might span across the end of one array and the start of another.\n\n# Approach\n1. **For `k == 1`**: This is a standard maximum subarray sum problem. We can solve this using Kadane\'s algorithm in linear time.\n   \n2. **For `k > 1`**:\n   - If the sum of the entire array is non-negative, it means concatenating the array will increase the total sum. The maximum subarray sum could either be from the concatenated circular subarrays or from the best subarray in the original array.\n   - If the total sum of the array is negative, concatenating multiple arrays does not help, so we should focus on finding the best subarray sum from within the single or circular versions of the array.\n\n   We calculate the maximum subarray sum for both the circular and non-circular cases, and handle the modulo operation to avoid overflow when `k > 2`.\n\n# Complexity\n- **Time complexity**:  \n  The time complexity is dominated by the linear passes through the array.  \n  For both `k == 1` and `k > 1`, the time complexity is $$O(n)$$ where `n` is the size of the array.\n\n- **Space complexity**:  \n  The space complexity is $$O(n)$$ due to the extra space used when doubling the array to handle the circular subarray calculation.\n\n# Code\n```cpp\nclass Solution {\nprivate:\n    const int MOD = 1e9 + 7;\n\n    int maxSubarraySumCircular(const vector<int>& nums) {\n        int n = nums.size();\n        int maxSum = INT_MIN, minSum = INT_MAX;\n        int totalSum = 0, currentMax = 0, currentMin = 0;\n\n        for (const int& num : nums) {\n            currentMax = max(currentMax + num, num);\n            maxSum = max(maxSum, currentMax);\n            \n            currentMin = min(currentMin + num, num);\n            minSum = min(minSum, currentMin);\n            \n            totalSum += num;\n        }\n\n        // Handle case where all elements are negative\n        if (maxSum <= 0) return *max_element(nums.begin(), nums.end());\n\n        return max(maxSum, totalSum - minSum);\n    }\n\n    int maxSubarraySumCircularDouble(const vector<int>& nums) {\n        vector<int> doubledArray(nums.begin(), nums.end());\n        doubledArray.insert(doubledArray.end(), nums.begin(), nums.end());\n\n        long long maxSum = 0, currentSum = 0;\n\n        for (const int& num : doubledArray) {\n            currentSum = max(currentSum + num, (long long)num);\n            maxSum = max(maxSum, currentSum);\n\n            if (currentSum < 0) currentSum = 0;\n        }\n\n        return maxSum % MOD;\n    }\n\npublic:\n    int kConcatenationMaxSum(vector<int>& arr, int k) {\n        int totalSum = accumulate(arr.begin(), arr.end(), 0LL);\n\n        if (k == 1) {\n            // Find the maximum subarray sum for a single array\n            int maxSingle = 0, currentSum = 0;\n            for (const int& num : arr) {\n                currentSum = max(currentSum + num, num);\n                maxSingle = max(maxSingle, currentSum);\n            }\n            return maxSingle;\n        } else {\n            if (totalSum >= 0) {\n                int maxSubSum = maxSubarraySumCircularDouble(arr);\n                long long result = maxSubSum;\n                result = (result + 1LL * (totalSum % MOD) * ((k - 2) % MOD)) % MOD;\n                return int(result);\n            } else {\n                int maxSubSum = maxSubarraySumCircular(arr);\n                return max(maxSubSum, 0);\n            }\n        }\n    }\n};\n```\n![image.png](https://assets.leetcode.com/users/images/16b07a39-afb8-472f-96fa-49b9b7d59080_1729539472.0076053.png)\n
['Array', 'C++']