Tìm dãy con xen kẽ có tổng lớn nhất 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. Nhiệm vụ là viết chương trình tìm dãy con xen kẽ có tổng lớn nhất bắt đầu từ phần tử đầu tiên của mảng.

Dãy con xen kẽ (alternating subsequence) là dãy con mà các phần tử tăng và giảm theo thứ tự xen kẽ: trước giảm, sau tăng, sau giảm... Dãy con xen kẽ ngược (tăng trước, giảm sau) không hợp lệ cho bài toán này.

Ví dụ minh họa

Đầu vào

arr[] = {5, 1, 6, 2, 4, 8, 9}

Đầu ra

27

Giải thích

Phần tử bắt đầu: 5, giảm: 1, tăng: 6, giảm: 2, tăng: 4, Kết thúc.
Ở đây ta có thể dùng 4, 8, 9 làm phần tử cuối cùng của dãy con.
Tổng = 5 + 1 + 6 + 2 + 4 + 9 = 27

Phương pháp giải

Để giải bài toán, ta sử dụng cách tiếp cận Quy hoạch động. Ta sử dụng hai mảng: một lưu tổng lớn nhất của các dãy con kết thúc tại arr[i] mà arr[i] đang tăng, mảng kia lưu tổng lớn nhất kết thúc tại arr[i] mà arr[i] đang giảm.

Sau đó thêm các phần tử một bằng một, kiểm tra xem chúng có tạo thành dãy con xen kẽ không. Với mỗi mảng, ta tính tổng lớn nhất đến chỉ số đó. Và trả về giá trị lớn nhất sau khi duyệt n phần tử.

Chương trình minh họa

#include <iostream>
#include <cstring>
using namespace std;

int maxVal(int x, int y) {
    if (x > y) return x;
    return y;
}

int calcMaxSumAltSubSeq(int arr[], int n) {
    int maxSum = -10000;
    int maxSumDec[n];
    bool isInc = false;
    memset(maxSumDec, 0, sizeof(maxSumDec));
    int maxSumInc[n];
    memset(maxSumInc, 0, sizeof(maxSumInc));
    
    maxSumDec[0] = maxSumInc[0] = arr[0];
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) {
                maxSumDec[i] = maxVal(maxSumDec[i], maxSumInc[j] + arr[i]);
                isInc = true;
            } else if (arr[j] < arr[i] && isInc)
                maxSumInc[i] = maxVal(maxSumInc[i], maxSumDec[j] + arr[i]);
        }
    }
    
    for (int i = 0; i < n; i++)
        maxSum = maxVal(maxSum, maxVal(maxSumInc[i], maxSumDec[i]));
    
    return maxSum;
}

int main() {
    int arr[] = {8, 2, 3, 5, 7, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Dãy con xen kẽ có tổng lớn nhất bắt đầu từ đầu là "
         << calcMaxSumAltSubSeq(arr, n);
    return 0;
}

Đầu ra

Dãy con xen kẽ có tổng lớn nhất bắt đầu từ đầu là 25