Problem: 1191. K-Concatenation Maximum Sum K 次串联后最大子数组之和

这道题没有官方题解

根据单个数组也就是k=1的情况下的动态规划递推公式：dp[i] = max(0, dp[i-1]) + arr[i]

总共分3种情况:

1、总和<=0，所以当k=2且求当i > 2 * n的最大值时，还是从0开始累加，也就是说明存在循环的，每个k最开始都是从arr[0]开始累加

2、数组所有数字都是正数，表示可以一直累加下去，所以可以直接求出答案

3、总和>0, 此时也是存在规律的，对求出的每个最大值，tmp中的每个tp都是等差数列，差值是sum，也就是tmp[i][0] - tmp[i-1][0] = sum, tmp[i][n-1] - tmp[i-1][n-1] = sum, ，所以拿到一个tp的最大值以后，就可以根据等差数列的公式求出结果

Code

class Solution {
public:
    const int mod = 1e9+10-3, zero = 0;
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long long n = arr.size(), sum = 0, dp = INT_MIN, mx = 0, di = 0;
        vector<int> array;
        bool allpos = true;
        vector<vector<int>> tmp;
        for(int& i : arr) {
            array.push_back((int)i);
            if(i <= 0) allpos = false;
            sum += i;
        }
        if(allpos > 0) return ((long long)sum * (long long) k) % mod;
        if(sum <= 0) k = min(k, 2);
        long long len = ((long long)n * (long long)k) % INT_MAX;
        vector<int> tp;
        int size = 2;
        for(long long i = 0; i < len; i++) {
            if(dp < 0) {
                dp = array[i%n];
            } else {
                dp = (dp + array[i%n]);
            }
            // if(i % n >= n-size) {
                tp.push_back(dp);
                if(tp.size()==n) {
                    tmp.push_back(tp);
                    tp.clear();
                }
            // }
            mx = max(dp, mx);
            if(mx > mod) return mx % mod;
            if(sum > 0 && tmp.size() == 2) break;
        }
        if(sum > 0 && tmp.size()==2) {
            int ind = 1;
            unsigned long long maxmax = *max_element(tmp[ind].begin(), tmp[ind].end());
            unsigned long long kk = maxmax + (unsigned long long)sum * (unsigned long long)(k - 1 - ind);
            return kk%mod;
        }
        return mx % mod;
    }
};