Tổng lớn nhất của dãy con luân phiên trong C++

Mô tả bài toán

Cho mảng số nguyên, tìm tổng lớn nhất của một dãy con luân phiên: giảm → tăng → giảm → tăng... (hoặc ngược lại).

Giải pháp (Quy hoạch động)

• dec[i] = tổng lớn nhất dãy con luân phiên kết thúc tại i với bước cuối là giảm.
• inc[i] = tổng lớn nhất dãy con luân phiên kết thúc tại i với bước cuối là tăng.
• Khởi tạo dec[0] = inc[0] = arr[0].
• Với mỗi i, duyệt j < i:
  • Nếu arr[j] > arr[i] → dec[i] = max(dec[i], inc[j] + arr[i]).
  • Nếu arr[j] < arr[i] và đã có bước giảm trước đó → inc[i] = max(inc[i], dec[j] + arr[i]).
• Kết quả = max của tất cả inc[i] và dec[i].

Ví dụ minh họa

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

int maxAlternateSum(int arr[], int n) {
    if (n == 1) return arr[0];
    int dec[n], inc[n];
    memset(dec, 0, sizeof(dec));
    memset(inc, 0, sizeof(inc));
    dec[0] = inc[0] = arr[0];
    int flag = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) { dec[i] = max(dec[i], inc[j] + arr[i]); flag = 1; }
            else if (arr[j] < arr[i] && flag == 1) inc[i] = max(inc[i], dec[j] + arr[i]);
        }
    }
    int result = INT_MIN;
    for (int i = 0; i < n; i++) {
        result = max(result, inc[i]);
        result = max(result, dec[i]);
    }
    return result;
}

int main() {
    int arr[] = {8, 2, 3, 5, 7, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << maxAlternateSum(arr, n) << endl;
    return 0;
}

Đầu ra

Maximum sum = 25