LeetCode 1191. K 次串联后最大子数组之和（前缀和+分类讨论）

Michael阿明

发布于 2021-09-06 10:16:06

2210

发布于 2021-09-06 10:16:06

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/k-concatenation-maximum-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

分三种情况

k=1, k = 2, k > 2

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        typedef long long ll;
        vector<ll> presum(arr.size()*2);
        ll ans = max(0, arr[0]), mod = 1e9+7, sum=0;
        ll MIN = min(0, arr[0]), n = arr.size();
        presum[0] = arr[0];
        for(int i = 1; i < n*2; ++i)
        {
            presum[i] = presum[i-1] + arr[i%n];//前缀和
            ans = max(ans, (ll) (presum[i]-MIN));
            //前缀和减去前面的最小的前缀和, 最大子数组和
            MIN = min(MIN, (ll) presum[i]);
            if(k==1 && i == n-1)
                return ans;// k=1，直接返回答案
            if(i==n-1)
                sum = presum[n-1];//记录单个完整数组的和
        }
        if(sum > 0)//和能带来收益
            return (ans+(k-2)*sum%mod)%mod;
        return ans;
    }
};

96 ms 44.1 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/03/19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https