Tìm tổng dãy con lớn nhất sao cho không có ba phần tử liên tiếp trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] gồm n số nguyên dương. Nhiệm vụ là viết chương trình tìm tổng dãy con lớn nhất sao cho không có ba phần tử liên tiếp.

Mô tả bài toán

Ở đây, ta cần tìm tổng của các dãy con tạo thành từ mảng sao cho không có ba phần tử liên tiếp nào.

Các phần tử liên tiếp

Các phần tử liên tiếp của một mảng là những phần tử tuân theo cùng thứ tự chỉ số: arr[0], arr[1], arr[2], ...

Ví dụ minh họa

Đầu vào

arr[] = {5, 9, 12, 15}

Đầu ra

32

Giải thích

Tổng = 5 + 12 + 15 = 32

Phương pháp giải

Cách đơn giản: tạo mảng phụ lưu tổng đến chỉ số hiện tại. Sau đó tìm tổng và kiểm tra tổng đến chỉ số bằng cách kiểm tra các tổng liên tiếp.

Giá trị tổng ban đầu:
sumVal[0] = arr[0]
sumVal[1] = arr[0] + arr[1]

Giá trị thứ ba không thể xét trực tiếp. Khi xét tổng, ta kiểm tra điều kiện với ba phần tử hiện tại: Nếu xét arr[i] làm tăng tổng, loại bỏ arr[i-1] hoặc arr[i-2]. Ngược lại không xét arr[i], tổng giữ nguyên.

sum[i] = max(sum[i-3] + arr[i-1] + arr[i], sum[i-2] + arr[i], sum[i-1])

Chương trình minh họa

#include <iostream>
using namespace std;

int findMaxSubSeqSum(int arr[], int n) {
    int maxSumArr[n];
    maxSumArr[0] = arr[0];
    maxSumArr[1] = arr[0] + arr[1];
    maxSumArr[2] = max(maxSumArr[1], max(arr[1] + arr[2], arr[0] + arr[2]));
    
    for (int i = 3; i < n; i++) {
        int sum1 = maxSumArr[i - 2] + arr[i];
        int sum2 = arr[i] + arr[i - 1] + maxSumArr[i - 3];
        maxSumArr[i] = max(max(maxSumArr[i - 1], sum1), sum2);
    }
    
    return maxSumArr[n - 1];
}

int main() {
    int arr[] = { 5, 9, 12, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tổng dãy con lớn nhất không có 3 phần tử liên tiếp là "
         << findMaxSubSeqSum(arr, n);
    return 0;
}

Đầu ra

Tổng dãy con lớn nhất không có 3 phần tử liên tiếp là 32