LeetCode-1191 K 次串联后最大子数组之和
题目描述：
给你一个整数数组 arr 和一个整数 k。
首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
举个例子，如果
arr = [1, 2]且k = 3，那么修改后的数组就是[1, 2, 1, 2, 1, 2]。
然后，请你返回修改后的数组中的最大的子数组之和。
注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大 ，所以需要 模（mod） 10^9 + 7 后再返回。
示例 1：
输入：arr = [1,2], k = 3
输出：9
AI写代码示例 2：
输入：arr = [1,-2,1], k = 5
输出：2
AI写代码示例 3：
输入：arr = [-1,-2], k = 7
输出：0
AI写代码提示：
1 <= arr.length <= 10^51 <= k <= 10^5-10^4 <= arr[i] <= 10^4
题目大意：
将原来的数组扩大为原来的k倍形成一个新的数组，问新数组的最大字段和。
思路：
此题很容易让人想到暴力，先形成新数组再对新数组调用最大字段和算法，其实复杂度还可以往下降，看到这道题我就想起了2019ACM山东省赛的C题名字貌似是Wandering Robot，这道题给我的感觉跟那道题很相似，都是分析一下“头”，分析一下“尾”，中间过程不用详细考究 。
对于这道题来说，上来先看一下原数组所有元素之和是否大于0。
如果大于0直观上则代表着k越大最后的字段和就越大，每一个周期都是可以使子段和增加的。此时最终的最大字段和就是中间k-2个周期的和，再加上第一个周期的尾和最后一个周期的头（前提是加上要使结果更大）；
如果小于0则直观上则代表着k越大最后的子段和就越小，这个时候可以计算两个周期的最大字段和（前提是k>=2），之所以计算两个周期的，是因为一个周期不足以代表最后的最大字段和。举个例子，原数组为{3,6 ,-50,-30,-20,1,5}，原数组的最大子段和是3+6=9，而两个周期合并后的数组为{3,6,-50,-30,-20,1,5,3,6 ,-50,-30,-20,1,5}，最大子段和为1+5+3+6=15。
如果k=1即只有一个周期，直接返回原数组的最大子段和即可 。
上AC代码：
class Solution {
public:
int dp[200000];
int kConcatenationMaxSum(vector<int>& arr, int k) {
int len=arr.size();
int num=0;
int i;
int ans=-0x3f3f3f3f;
memset(dp,0,sizeof(dp));
for(i=0;i<len;i++)
{
if(i>0&&dp[i-1]>0)
{
dp[i]=max(dp[i-1]+arr[i],dp[i]);
}
else
{
dp[i]=max(dp[i],arr[i]);
}
if(dp[i]>ans)
{
ans=dp[i];
}
num+=arr[i];
}
if(k>1&&num>0)
{
int sum1=0;
int ans1=0;
int sum2=0;
int ans2=0;
for(i=len-1;i>=0;i--)
{
sum1+=arr[i];
if(sum1>ans1)
{
ans1=sum1;
}
}
for(i=0;i<len;i++)
{
sum2+=arr[i];
if(sum2>ans2)
{
ans2=sum2;
}
}
long long int res=(long long int)num*(k-2)+ans1+ans2;
return res%(1000000007);
}
else if(k>1)
{
for(i=len;i<2*len;i++)
{
arr.push_back(arr[i-len]);
if(i>0&&dp[i-1]>0)
{
dp[i]=max(dp[i-1]+arr[i],dp[i]);
}
else
{
dp[i]=max(dp[i],arr[i]);
}
if(dp[i]>ans)
{
ans=dp[i];
}
}
return ans;
}
else
{
return ans;
}
}
};
AI写代码