1191. K 次串联后最大子数组之和（最大子段和变形）_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
示例 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
这个题目，还是要求最大子段和。
①整个数组的和大于0，那么最大值就是sum*(k-1)+max1(原始数组中的最大子段和).
②在整体和不大于0大的情况下，最大值就在max1,max2(连续两段数组的最大子段和)中取到了。
第二种情况一开始想了好多种情况，分类讨论了很多。但是最后才发现，其实就是在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的时候，才可以构建两个数组
        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;//可能有人会想，为什么不是K*sum，其实x>=k*sum，所以直接写x就可以了。
            x%=mod;
            int y=(int)x;
            return y;
        }
        else return max(max1,max2);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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