1191. K-Concatenation Maximum Sum¶
题目信息¶
- 题号:
1191
- 难度:
Medium
- 主题:
数组、最大子数组、重复拼接
- 原题:
- 重点:
把
arr连续拼接k次后求最大连续子数组和;允许选择空子数组得到0,结果对10^9+7取模
题目重述¶
给定整数数组 arr 和正整数 k。构造新数组,使其由 arr 按原顺序连续拼接 k 次组成。
请返回新数组中连续子数组能够得到的最大元素和。允许选择长度为 0 的子数组,此时和为 0,因此答案不会为负数。最终结果对 10^9 + 7 取模。
1 <= arr.length <= 10^5,1 <= k <= 10^5,-10^4 <= arr[i] <= 10^4。
自建示例¶
最优区间跨越多个副本:
输入:arr = [2,-1], k = 3
输出:4
解释:拼接后为 [2,-1,2,-1,2,-1],选择前五个元素得到最大和 4。
全部元素为负数:
输入:arr = [-2,-1], k = 4
输出:0
解释:任何非空连续子数组的和都为负数,选择空子数组得到 0。