1191. K-Concatenation Maximum Sum

题目信息

题号:

1191

难度:

Medium

主题:

数组、最大子数组、重复拼接

原题:

LeetCode 1191

重点:

把 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。