C语言重构【1191】K 次串联后最大子数组之和-蒲公英云

C语言重构【1191】K 次串联后最大子数组之和

文章目录

- - - 所有题目源代码：[Git地址](https://github.com/ch98road/leetcode)
    - 题目
    - 方案：
    - - 复杂度计算

所有题目源代码：Git地址

题目

给你一个整数数组 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

方案：

class Solution
{ 
public:
    int kConcatenationMaxSum(vector<int> &arr, int k)
    { 
        int len = arr.size();
        int res = 0, now = 0;
        int lastres = 0;
        //跑k轮
        for (int i = 0; i < k; i++)
        { 
            lastres = res;
            for (int j = 0; j < len; j++)
            { 
                now = (arr[j] + now) > 0 ? (arr[j] + now) : 0;
                if (now >= 1000000007)
                { 
                    now = now % (1000000007);
                    res = now;
                }
                else
                    res = max(now, res);
            }
            //如果一圈下来没涨，那么剩下的圈也不用跑了，不会涨
            if (res == lastres)
                break;
            //一圈下来涨了，当i>1的时候（说明是整圈跑下来的）那么直接加整圈即可
            else if (res > lastres && i > 1)
            { 
                int tmp = res - lastres;
                for (int j = i + 1; j < k; j++)
                { 
                    res = (res + tmp) % (1000000007);
                }
                break;
            }
        }
        return res;
    }
};