JAVA程序设计（K|JAVA程序设计：K 次串联后最大子数组之和（LeetCode：1191））
给你一个整数数组 arr 和一个整数 k。
首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
然后，请你返回修改后的数组中的最大的子数组之和。
注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。
示例 1：
【JAVA程序设计（K|JAVA程序设计：K 次串联后最大子数组之和（LeetCode：1191））】输入：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[i] <= 10^4
思路：和最大数组和一样，只是多了几次循环而已，我们知道，当循环次数大于等于2的时候，答案需要在原本不循环的基础上与两种情况进行比较：
情况①：当该数组的总和小于等于0时，最大值可能为该数组的最大后缀+最大前缀和。
情况②：当该数组的总和大于0时，最大值可能为该数组的最大后缀+最大前缀和+(k-2)*总和。
class Solution {final static int mod = 1000000007;
public int kConcatenationMaxSum(int[] arr, int k) {long ans, sum;
int n = arr.length;
ans = Math.max(0, arr[n - 1]);
long tmp1 = 0, tmp2 = 0;
sum = 0;
for (int i = 0;
i < n;
i++) {
sum += arr[i];
tmp1 = Math.max(sum, tmp1);
}sum = 0;
for (int i = n - 1;
i >= 0;
i--) {
sum += arr[i];
tmp2 = Math.max(sum, tmp2);
}if (k > 1)
ans = Math.max(ans, tmp1 + tmp2 + (k - 2) * (sum > 0 ? sum : 0));
sum = 0;
for (int i = 0;
i < n;
i++) {
sum += arr[i];
ans = Math.max(ans, sum);
if (sum < 0) sum = 0;
}return (int) (ans % mod);
}
}推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 眼观耳听美食的日子
- 【故障公告】周五下午的一次突发故障
- 我要我们在一起（二）
- 基于|基于 antd 风格的 element-table + pagination 的二次封装
- 事件代理
- 粪娃嫫
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 洱海不是海，，人群没有你