Given an integer array arr
and an integer k
, modify the array by repeating it k
times.
For example, if arr = [1, 2]
and k = 3
then the modified array will be [1, 2, 1, 2, 1, 2]
.
Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0
and its sum in that case is 0
.
As the answer can be very large, return the answer modulo 10^9 + 7
.
Example 1:
Input: arr = [1,2], k = 3 Output: 9
Example 2:
Input: arr = [1,-2,1], k = 5 Output: 2
Example 3:
Input: arr = [-1,-2], k = 7 Output: 0
Constraints:
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
Solution: DP
This problem can be reduced to maxSubarray.
If k < 3: return maxSubarray(arr * k)
ans1 = maxSubarray(arr * 1)
ans2 = maxSubarray(arr * 2)
ans = max([ans1, ans2, ans2 + sum(arr) * (k – 2)])
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int kConcatenationMaxSum(vector<int>& arr, int k) { constexpr int kMod = 1e9 + 7; auto maxSum = [&arr](int r) { long sum = 0; long ans = 0; for (int i = 0; i < r; ++i) { for (long a : arr) { sum = max(0L, sum += a); ans = max(ans, sum); } } return ans; }; if (k < 3) return maxSum(k) % kMod; long ans1 = maxSum(1); long ans2 = maxSum(2); long sum = accumulate(begin(arr), end(arr), 0L); return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment