Tổng lớn nhất mảng con sau khi nối mảng lặp lại K lần trong C++

Mô tả bài toán

Cho mảng a[] và số nguyên K. Tạo mảng mới bằng cách lặp lại a đúng K lần. Tìm tổng lớn nhất của mảng con liên tiếp trong mảng mới này.

Giải pháp (Kadane trên mảng ảo)

• Không cần tạo mảng thực tế, dùng chỉ số modulo: a[i % n].
• Áp dụng thuật toán Kadane trên n*K phần tử ảo.
• Độ phức tạp O(N×K), không gian O(1).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int maxSubArraySumRepeated(int a[], int n, int k) {
    int max_so_far = INT_MIN, max_ending_here = 0;
    for (int i = 0; i < n * k; i++) {
        max_ending_here += a[i % n];
        max_so_far = max(max_so_far, max_ending_here);
        if (max_ending_here < 0) max_ending_here = 0;
    }
    return max_so_far;
}

int main() {
    int a[] = {10, 20, -30, -1};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;
    cout << "Maximum contiguous sum is " << maxSubArraySumRepeated(a, n, k);
    return 0;
}

Đầu ra

Maximum contiguous sum is 30