1191 K-Concatenation Maximum Sum K 次串联后最大子数组之和
Description:
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 109 + 7.
Example:
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 <= 10^4
标题形貌:
给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
比方，假如 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。
返回修改后的数组中的最大的子数组之和。留意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果大概会很大，须要返回的 109 + 7 的 模 。
示例 :
示例 1：
输入：arr = [1,2], k = 3
输出：9
示例 2：
输入：arr = [1,-2,1], k = 5
输出：2
示例 3：
输入：arr = [-1,-2], k = 7
输出：0
提示:
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr <= 10^4
思路:
模仿
当 k = 1 时, 转化为最大连续子数组和, 留意答案非负
当 k = 2 时, 为数组最大前缀和和最大后缀和的和
当 k > 2 时, 假如数组的和为正, 须要加上 sum * (k - 2)
时间复杂度为 O(n), 空间复杂度为 O(n)
代码:
C++: |
