problem:1191. K 次串联后最大子数组之和

思路：这题是最大子数组和的变形题（见我以前的题解），这题的思路和最大子数组完全一样，但是就是数据范围很大，如果直接在arr数组后边插入的话内存会不够。对于重复次数为1的数组，直接套模板即可，对于重复次数大于等于2的情况，最终答案必定在以下几种可能中：

• 单个arr数组的子数组最大值就是答案，不管重复多少次都是这样。
• 以第一个arr数组的末尾m个数的子数组的最大值+(k-2)*sum(arr)+以最后一组arr的开头n个数的子数组的最大值。 即$f[len(arr)]+(k-2)*sum(arr)+max(presumarr)$ (其中f[i]为以i结尾子数组最大和或者max(sufsum))
• 还有一种情况就是中间的很多节都没有用只要第一第二节。ans = max(ans,f[arr.size()]+maxpre);

以上包含所有情况

Accode:

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        vector<long long > presum(1,0);
        bool all_below = true;
        long long maxpre = -0x3f3f3f3f;
        for(auto it:arr){
            if(it>0) all_below = false;
            presum.push_back(presum.back()+it);
            maxpre = max(maxpre,presum.back());    
        }
        if(all_below) return 0;
        long long ans=0;
        int mod = 1e9+7;
        vector<long long> f(arr.size()+1,0);
        for(int i=0;i<arr.size();i++){
            f[i+1] = max(f[i],0LL)+arr[i];
            ans = max(ans,f[i+1]);
        }
        if(k==1) return ans>0?ans%mod:0;
        if(k>=2) {
            ans = max(ans,f[arr.size()]+maxpre);
            ans = max(f[arr.size()]+presum[arr.size()]*(k-2)+maxpre,ans);
            return ans>0?ans%mod:0;
        }
        return 0;
    }
};

时间复杂度：$o(n)$