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

Trong bài toán này, chúng ta được cung cấp một mảng arr[] kích thước n và một số nguyên k. Nhiệm vụ là viết chương trình tìm tổng mảng con lớn nhất trong mảng được tạo sau khi nối lặp lại.

Mô tả bài toán

Chúng ta sẽ tìm tổng lớn nhất của mảng con được lấy từ mảng mới được tạo sau khi lặp lại mảng arr k lần.

Ví dụ minh họa

Đầu vào

arr[] = {-9, -5, 14, 6}
k = 2

Đầu ra

26

Giải thích

Mảng mới sau khi lặp: {-9, -5, 14, 6, -9, -5, 14, 6}
Mảng con có tổng lớn nhất = {14, 6, -9, -5, 14, 6}
Tổng = 26

Phương pháp giải

Cách đơn giản: tạo mảng mới được hình thành sau khi nối arr[] k lần, sau đó tìm mảng con có tổng lớn nhất. Phương pháp tốt nhất là sử dụng thuật toán Kadane.

Chương trình minh họa (Cách 1)

#include <iostream>
using namespace std;

int calcMaxSubArraySum(int arr[], int n, int k) {
    int newArr[2*n];
    for (int i = 0; i < k*n; i++)
        newArr[i] = arr[i%n];
    
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k*n; i++) {
        sum = sum + newArr[i];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main() {
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tổng mảng con lớn nhất sau khi nối lặp lại là "
         << calcMaxSubArraySum(arr, n, k);
    return 0;
}

Đầu ra

Tổng mảng con lớn nhất sau khi nối lặp lại là 26

Cách này tốt nhưng có cách hiệu quả hơn sử dụng số học modulo.

Số học modulo (Modular Arithmetic)

Là sử dụng phép toán modulo để lấy phần dư của phép chia.

Để giải bài toán, ta sử dụng số học modulo thay vì tạo mảng bằng cách nối lặp lại. Phần giải còn lại giữ nguyên.

Chương trình minh họa (Cách 2 - Hiệu quả hơn)

#include <iostream>
using namespace std;

int calcMaxSubArraySum(int arr[], int n, int k) {
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k*n; i++) {
        sum = sum + arr[i%n];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main() {
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tổng mảng con lớn nhất sau khi nối lặp lại là "
         << calcMaxSubArraySum(arr, n, k);
    return 0;
}

Đầu ra

Tổng mảng con lớn nhất sau khi nối lặp lại là 26