Tổng lớn nhất mảng lặp K lần trong C++

Mô tả bài toán

Cho mảng arr và số k. Tạo mảng mới bằng cách lặp arr đúng k lần. Tìm tổng lớn nhất của dãy con liên tiếp (có thể rỗng, tổng = 0). Kết quả modulo 1e9+7.

Ví dụ: arr=[1,-2,1], k=5 → kết quả 2.

Giải thuật Kadane mở rộng

Xét 3 trường hợp:

1. k = 1: Chạy Kadane trên arr.
2. sum(arr) > 0: Tổng lớn nhất có thể trải qua nhiều bản sao. Kết quả = max(kadane(arr), suffix_max + prefix_max + (k-2)*sum).
3. sum(arr) ≤ 0: Không nên lấy toàn bộ bản sao trung gian. Kết quả = max(kadane(arr), suffix_max + prefix_max).

Trong đó: prefix_max = tiền tố lớn nhất, suffix_max = hậu tố lớn nhất.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

class Solution {
    int kadane(vector<int>& a) {
        long long cur = 0, best = 0;
        for (int x : a) {
            cur = max(0LL, cur + x);
            best = max(best, cur);
        }
        return best % MOD;
    }
    int sum(vector<int>& a) {
        long long s = 0;
        for (int x : a) s = (s + x) % MOD;
        return s;
    }
    int prefix_max(vector<int>& a) {
        long long cur = 0, best = 0;
        for (int x : a) {
            cur = (cur + x) % MOD;
            best = max(best, cur);
        }
        return best;
    }
    int suffix_max(vector<int>& a) {
        long long cur = 0, best = 0;
        for (int i = a.size()-1; i >= 0; i--) {
            cur = (cur + a[i]) % MOD;
            best = max(best, cur);
        }
        return best;
    }
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int kd = kadane(arr);
        if (k == 1) return kd;
        int sm = sum(arr), pre = prefix_max(arr), suf = suffix_max(arr);
        if (sm > 0) {
            long long mid = (1LL * (k-2) * sm) % MOD;
            return max(kd, (int)((mid + pre + suf) % MOD));
        }
        return max(kd, (pre + suf) % MOD);
    }
};

int main() {
    vector<int> v = {1,-2,1};
    Solution ob;
    cout << ob.kConcatenationMaxSum(v, 5); // 2
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).