Maximum Subarray Sum in Repeated Copies

### Problem Concatenate k copies of arr and find the largest contiguous-subarray sum. The empty subarray is allowed and has sum 0. Return the maximum sum modulo 1000000007; optimize the actual sum before taking its residue. ```cpp class Solution { public: int kConcatenationMaxSum(vector<int>& arr, int k); }; ``` ### Examples **Example 1:** ```text Input: arr = [2,-1], k = 4 Output: 5 Explanation: The repeated array starts2,-1,2,-1,2,-1,2,-1. Omitting the final-1 gives sum5. ``` **Example 2:** ```text Input: arr = [-3,2], k = 3 Output: 2 Explanation: Each full copy has negative sum, so joining additional copies cannot improve on a single2. ``` ### Constraints - Both arr.length and k lie between 1 and 100000. - Each original value is an integer in `[-10000,10000]`. ### Contract considerations Account for both the original length and the repetition count when bounding time and memory. The requested result is a sum, not the expanded array. ```hint Read the boundary condition If every entry is negative, is an empty subarray still permitted, and when is the modulus applied? ``` ### Boundary reminders Account for both the original length and the repetition count when bounding time and memory. The requested result is a sum, not the expanded array.