給你一個(gè)整數(shù)數(shù)組 arr 和一個(gè)整數(shù) k。

首先，我們要對(duì)該數(shù)組進(jìn)行修改，即把原數(shù)組 arr 重復(fù) k 次。

舉個(gè)例子，如果 arr = [1, 2] 且 k = 3，那么修改后的數(shù)組就是 [1, 2, 1, 2, 1, 2]。

然后，請(qǐng)你返回修改后的數(shù)組中的最大的子數(shù)組之和。

注意，子數(shù)組長(zhǎng)度可以是 0，在這種情況下它的總和也是 0。

由于 結(jié)果可能會(huì)很大，所以需要 模（mod） 10^9 + 7 后再返回。

示例 1：

輸入：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
這個(gè)題目，還是要求最大子段和。
①整個(gè)數(shù)組的和大于0，那么最大值就是sum*(k-1)+max1(原始數(shù)組中的最大子段和).
②在整體和不大于0大的情況下，最大值就在max1,max2(連續(xù)兩段數(shù)組的最大子段和)中取到了。
第二種情況一開(kāi)始想了好多種情況，分類討論了很多。但是最后才發(fā)現(xiàn)，其實(shí)就是在max1和max2中取到。
代碼如下：

class Solution { public:int mod=1e9+7;int getmax(vector<int>& arr)//得到最大子段和{int _max=0;int sum=0;for(int i=0;i<arr.size();i++){sum=sum+arr[i];sum%=mod;_max=max(_max,sum)%mod;if(sum<0) sum=0;}return _max%mod;}int kConcatenationMaxSum(vector<int>& arr, int k) {int sum=0;vector<int> arr2;int t=2;if(k>=2)//只有在k>=2的時(shí)候，才可以構(gòu)建兩個(gè)數(shù)組while(t--){for(int i=0;i<arr.size();i++) arr2.push_back(arr[i]);}int max1=getmax(arr);int max2=getmax(arr2);for(int i=0;i<arr.size();i++){sum=(sum+arr[i])%mod;}if(sum>0) {long long x=((long long)(k-1)*(long long)sum)+max1;//可能有人會(huì)想，為什么不是K*sum，其實(shí)x>=k*sum，所以直接寫(xiě)x就可以了。x%=mod;int y=(int)x;return y;}else return max(max1,max2);} };

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的1191. K 次串联后最大子数组之和（最大子段和变形）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。