Tổng dãy con lớn nhất trong mảng được lặp lại k lần trong C++

Trong bài toán này, chúng ta được cho một mảng và một số k. Nhiệm vụ là viết chương trình tìm tổng dãy con liên tiếp lớn nhất trong mảng được hình thành bằng cách lặp lại mảng gốc k lần.

Mô tả bài toán – Tìm tổng lớn nhất của dãy con được tạo từ mảng lặp lại k lần.

Ví dụ để hiểu rõ hơn:

Đầu vào – mảng = {3, 5, 1}, k = 2

Đầu ra – 18

Giải thích –

Mảng sau khi lặp k lần: {3, 5, 1, 3, 5, 1}
Tổng dãy con lớn nhất = 3+5+1+3+5+1 = 18

Để giải quyết, ta tính tổng tất cả các phần tử của mảng. Dựa vào tổng này, ta xác định tổng dãy con:

• Nếu tổng > 0: nhân tổng mảng với k lần để được tổng thực tế.
• Nếu tổng < 0: tìm dãy con có tổng lớn nhất bằng cách lấy 2 lần lặp mảng.

Mã nguồn C++

#include<iostream>
using namespace std;

void repeatArray(int *arr, int *b, int k, int len) {
    int j = 0;
    while (k > 0) {
        for (int i = 0; i < len; i++)
            b[j++] = arr[i];
        k--;
    }
}

long subArraySum(int *a, int len) {
    int max = 0;
    long newmax = 0;
    for (int i = 0; i < len; i++) {
        newmax = newmax + a[i];
        if (max < newmax)
            max = newmax;
        if (newmax < 0)
            newmax = 0;
    }
    return max;
}

long findMaxSubArraySum(int *arr, int k, int len) {
    int arraySum = 0;
    long maxSum = 0;
    int b[(2 * len)] = {0};
    repeatArray(arr, b, 2, len);
    for (int i = 0; i < len; i++)
        arraySum += arr[i];
    maxSum = subArraySum(b, 2 * len);
    if (arraySum > 0)
        maxSum = subArraySum(b, 2 * len) + (k - 2) * arraySum;
    return maxSum;
}

int main() {
    int arr[] = {3, 5, 1};
    int length = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "The maximum subarray sum in array formed by repeating the given array " << k << " times is " << findMaxSubArraySum(arr, k, length);
    return 0;
}

Kết quả

The maximum subarray sum in array formed by repeating the given array 3 times is 27