Description

Submission

typedef long long ll;
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        const int M = 1e9 + 7;
        vector<ll> nums(arr.begin(), arr.end());
        copy(arr.begin(), arr.end(), back_inserter(nums));
        
        ll total = 0, ret = 0;
        for(auto x: arr) {
            total += x;
        }
        
        arr.insert(arr.begin(), 0);
        arr.push_back(0);
        int n = arr.size();
        
        vector<ll> presum(n);
        
        presum[0] = arr[0];
        for(int i = 1; i < n; ++i) {
            presum[i] = presum[i-1] + arr[i];
        }
        
        ll sum = 0;
        ll maxPresum = 0;
        for(int i = 0; i < n; ++i) {
            maxPresum = max(presum[n-1] - presum[i], maxPresum);
        }
        
        ll maxPostsum = 0;
        for(int i = 0; i < n; ++i) {
            maxPostsum = max(presum[i] - presum[0], maxPostsum);
        }
        
        ll maxOneWaySum = 0;
        sum = 0;
        for(auto x: arr) {
            sum = max(sum + x, (ll)0);
            maxOneWaySum = max(sum, maxOneWaySum);
        }
        
        if(k == 1) {
            return maxOneWaySum % M;
        }
        
        if(total > 0) {
            return ((k - 2) * total + maxPresum + maxPostsum) % M;
        }

        sum = 0;
        for(ll x: nums) {
            sum = max((ll)0, sum + x);
            ret = max(sum, ret);
        }
        return ret % M;
    }
};