本文主要是介绍leetcode 1191.k次串联后最大子数组之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先上一下暴力dp解法，也就是直接延展dp数组得出来的结果：
class Solution {
public:int kConcatenationMaxSum(vector<int>& arr, int k) {int n=arr.size();vector<int>dp(n*k,0);int res=0;dp[0]=arr[0];res=max(dp[0],res);for(int i=1;i<arr.size()*k;i++){if(dp[i-1]<=0)dp[i]=arr[i%n]%1000000007;elsedp[i]=(dp[i-1]+arr[i%n])%1000000007;res=max(res,dp[i])%1000000007;}return res;}
};这种方法虽然说对，但是对于很大的数据来说，效率很低，会超限。
接下来就是对于此的优化问题。
首先k=1的时候，这就是普通的最大子数组和，直接dp就行了。
但是呢，对于k>=2的时候，我们就需要注意了，最大子数组和是不是延展到了多个数组呢？
首先想一下k==2的时候，这个时候其实我们直接相当于把两个数组拼接上就行了，然后dp就可以；
k的数值变大之后，我们还有两种情况需要谈论一下：当这个数组的全部元素和>0的时候，我们其实可以这样想：把剩下的k-2个数组插入到这两个数组中间，贡献子数组和的数值。因为无论如何，在k==2的基础之上，我们的加入数值>0的元素肯定是对于最后结果有帮助的，也就是最优问题的堆积。
但是呢，如果说这里的元素和是<0的。这个时候就不行了，我们就需要抛弃这些k-2个数组了，直接不选它们，还是以刚刚k==2的情况为最优情况就行了。（如果有疑问说为什么不和k==1的时候做比较呢？其实k==2的情况也包含了这种情况了，但不排除拼接之后会有更好的结果，所以以k==2为最优结果）
注意：数据可能会暴，所以想着用long来转换一下。
class Solution {
public:int kConcatenationMaxSum(vector<int>& arr, int k) {int n=arr.size();int sum=0;int f=0;int ans=0;if(k==1){for(int i=0;i<n;i++){f=max(f,0)+arr[i];ans=max(f,ans);}}else{for(int i=0;i<2*n;i++){f=max(f,0)+arr[i%n];ans=max(f,ans);}for(int i=0;i<n;i++){sum+=arr[i];}if(sum>0){ans=(ans+(k-2ll)*sum)%1000000007;}}return ans;}
};这篇关于leetcode 1191.k次串联后最大子数组之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
