返回信息流1.Given an integer array arr and an integer k, modify the array by repeating it k times.
2.For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
3.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.
4.As the answer can be very large, return the answer modulo 10^9 + 7.
自己写的代码老是通不过，看了一个通过的写的分析，跟自己的一样，但是自己的就是通不过，一脸懵逼。以下是我的代码逻辑：
1.判断 输入arr的长度
2.判断 k 是否为零
3.判断输入数组 arr是否全员小于等于零
4.判断 输入数组arr的累加之和与零的关系
4-1：若sum大于零，则先求出 k=2 时的最大子数组之后，然后加上 （k-2）*sum,若大于10^9+7,则取模
4-2：若sum小于零，则只需求出 k=2 时的最大子数组的值，同上
public static int kConcatenationMaxSum(int[] arr, int k) {
/** arr长度判断 **/
if (arr.length < 1)
return 0;
else {
/** k 值判断 **/
if(k == 0)
return 0;
else {
/** 返回0的条件 **/
int num = 0; // arr小于0的元素个数
int sum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] <= 0) {
num++;
}
sum = sum + arr[i];
}
/** arr 是否全员小于0 **/
if(num == arr.length)
return 0;
else {
/** 对 arr[] 整体累加之和判断 **/
if(sum > 0){
if(k == 1)
return findThemaxSubArr(arr);
else {
int[] newArr = new int[arr.length * 2];
for (int i =0; i < arr.length; i++){
newArr[i] = arr[i];
newArr[i+arr.length] = arr[i];
}
if((sum * k) > (findThemaxSubArr(newArr) + sum *(k-2)))
return sum*k;
else return (findThemaxSubArr(newArr) + sum*(k-2)) % 1000000007;
}
}
else {
/** arr 整体累加小于等于0 **/
if(k == 1)
return findThemaxSubArr(arr);
else {
int[] newArr = new int[arr.length * 2];
for (int i =0; i < arr.length; i++){
newArr[i] = arr[i];
newArr[i+arr.length] = arr[i];
}
return findThemaxSubArr(newArr) % 1000000007;
}
}
}
}
}
}
private static int findThemaxSubArr(int[] nums){
int sumMax = 0;
for(int i = 0; i < nums.length; i++){
int j = i;
int sum = 0;
while (j < nums.length){
sum = sum + nums[j];
if(sum > sumMax)
sumMax = sum;
j++;
}
}
return sumMax;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #98389同步于 2019/9/24
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【求助】leetcode上：求重复数组的最大子数组
biphoton
2019/9/24镜像同步9 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
【 在 laplace 的大作中提到: 】
k >= 2 且 sum 大于零时的最大子数组和计算方法不对，应该是 arr 的最大前缀和加上最大后缀和，再加上 (k-2)*sum。然后和 k = 1时的最大子数组和比较，二者取其大。
k >= 2 时，我的方法是：
1.将arr再重复一次，相当于 k=2时的新数组，然后找出此时的最大子数组，再加上 sum*(k-2)，这个值肯定是要大于 k=1时的最大子数组。
我对于您提出的方法的疑惑：
1.最大前缀和最大后缀和，这个是什么数学原理呢。我看那个discuss区有人使用这种算法，奈何数学底子薄，推导不出来为啥，有点迷糊。
2.我那种计算方法错误的时候，有啥特例呢？我自己选了一些特例计算 k >= 2时的值，没发现有问题，麻烦您指正一下。
【 在 intmain 的大作中提到: 】
: 考虑溢出了吗
sum溢出吗？我看讨论区那些人都没有考虑这个，只是考虑了题意中取100000007模的这个问题
分类讨论
1. 结果为0的情况
2. 结果为整个数列相加的情况
3. 结果为单个循环节的最大子数组和
4. 结果为两个循环节的最大子数组和
5. 结果为第一个循环节的后辍 + (k - 2)个循环节 + 最后一个循环节的前辍
此题坑点：
1. 返回值是int，其实是long long计算，最后取模
2. 这种题目设定真的是有病
```cpp
typedef long long llint;
const int MOD = 1000000000 + 7;
class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
const int n = arr.size();
llint res = 0;
llint t = accumulate(arr.begin(), arr.end(), 0);
res = max(res, t * k);
{
llint tot = 0;
llint mini = 0;
for (int i = 0; i < n; i++) {
tot += arr[i];
res = max(res, tot - mini);
mini = min(tot, mini);
}
}
if (k >= 2) {
llint l = 0;
llint r = 0;
llint totl = 0;
for (int i = 0; i < n; i++) {
totl += arr[i];
l = max(l, totl);
}
llint totr = 0;
for (int i = n - 1; i >= 0; i--) {
totr += arr[i];
r = max(r, totr);
}
res = max(res, l + r);
res = max(res, l + r + 1LL * (k - 2) * t);
}
return res % MOD;
}
};
```
我觉得基本的算法是对的，但是这个整体累加之和大于零时，如果sum*k>findTheMaxSubArr(newArr)+sum*（k-2)时返回sum*k，这个点不用模吗？我觉得不模也还是有错误的风险呀。
还有，findTheMaxSubArr函数里，如果sumMax溢出了怎么办，你这个程序其实根本没有处理溢出情况，最后处理的那一下有啥用我建议long long 安排上。
【 在 biphoton (石头今晚不吃饭) 的大作中提到: 】
: 1.Given an integer array arr and an integer k, modify the array by repeating it k times.
: 2.For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
: 3.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.
: ...................
这道题我做过... 当时刚了好几个小时刚出来了，我的思路就是这样... 具体的实现可能不一样
【 在 rhd (欣欣向荣) 的大作中提到: 】
: 最后，函数名字太特么长了啊，用手机打的我都快自闭了
因为k等于2时，只有三种种最大情况
1.单一的一个数组的最大sum和
2.两个数组，第一个取最大后缀和，第二个取最大前缀和
3.两个sum相加
不过你用了额外的数组空间.. 不需要这么考虑
可以试试用下long，而且对中间结果直接模，感觉思路应该没问题
【 在 biphoton (石头今晚不吃饭) 的大作中提到: 】
: k >= 2 且 sum 大于零时的最大子数组和计算方法不对，应该是 arr 的最大前缀和加上最大后缀和，再加上 (k-2)*sum。然后和 k = 1时的最大子数组和比较，二者取其大。
: k >= 2 时，我的方法是：
: ...................
完全没有什么数学原理的事。。。你算一下［1，-1，2］，k=3的情况就知道了～
以及目测他回答的也遗漏了一点小问题，这道题里要为了防止溢出每一步都得mod，但是在比较的时候又必须得比较原始值。k=1的时候的最大子数组和应该是小于longlongint的最大值的，在计算前缀和加后缀和加(k-2）*sum的时候可以每一步mod的时候记录一下商的部分，以便最后用于比较。（随便说一个，也许还有更方便的方法？）
【 在 biphoton 的大作中提到: 】
: