Tổng con mảng vòng lớn nhất trong C++

Cho mảng số nguyên (có thể âm). Tìm tổng lớn nhất của subarray trong mảng vòng (circular), tức là subarray có thể lấy từ cuối nối đầu.

Ví dụ: {1,2,8,4,3,0,7} → 22 (subarray 7,1,2,8,4).
{2,5,-1,6,9,4,-5} → 25 (subarray 4,2,5,-1,6,9).

Giải thuật (Kadane biến thể):

• Tính total = tổng mảng.
• Tìm max_subarray (Kadane thường) và min_subarray.
• Nếu min_subarray == total (toàn âm) thì trả về max_subarray.
• Ngược lại trả về max(max_subarray, total - min_subarray).

Ví dụ

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

int maximum(int arr[], int size) {
    int total = 0;
    for (int i = 0; i < size; i++) total += arr[i];
    int max_ending = arr[0], max_so_far = arr[0];
    int min_ending = arr[0], min_so_far = arr[0];
    for (int i = 1; i < size; i++) {
        max_ending = max(max_ending + arr[i], arr[i]);
        max_so_far = max(max_so_far, max_ending);
        min_ending = min(min_ending + arr[i], arr[i]);
        min_so_far = min(min_so_far, min_ending);
    }
    if (size == 1) return arr[0];
    if (min_so_far == total) return max_so_far;
    return max(max_so_far, total - min_so_far);
}

int main() {
    int arr[] = {2,5,-1,6,9,4,-5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum circular subarray sum is: " << maximum(arr, size);
    return 0;
}

Đầu ra

Maximum circular subarray sum is: 25