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

约定不等于承诺〃 2022-11-06 15:00 406阅读 0赞

### 文章目录 ###

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

#### 所有题目源代码：[Git地址][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;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n+k)：看起来是两层循环，实际上，i不会超过3，也就是最多3n+k的时间复杂度
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode