Tìm tích lớn nhất của dãy con tăng dần 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. Nhiệm vụ là tìm tích lớn nhất của một dãy con tăng dần.

Mô tả bài toán

Chúng ta cần tìm tích lớn nhất của dãy con tăng dần bất kỳ kích thước nào từ các phần tử của mảng.

Ví dụ minh họa

Đầu vào

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

Đầu ra

2160

Giải thích

Các dãy con tăng dần:
{5, 6, 8, 9}. Tích = 2160
{5, 6, 7, 9}. Tích = 1890
Ở đây chỉ xét dãy con kích thước lớn nhất.

Phương pháp giải

Cách đơn giản: sử dụng Quy hoạch động. Ta lưu trữ tích lớn nhất của dãy con tăng dần đến phần tử hiện tại của mảng và lưu trong một mảng.

Thuật toán

Khởi tạo

prod[] với các phần tử của arr[].
maxProd = -1000

Bước 1

Vòng lặp i từ 0 đến n-1

Bước 1.1

Vòng lặp j từ 0 đến i-1

Bước 1.1.1

Kiểm tra nếu phần tử hiện tại tạo dãy con tăng dần: arr[i] > arr[j] và arr[i]*prod[j] > prod[i] -> prod[i] = prod[j]*arr[i]

Bước 2

Tìm phần tử lớn nhất của mảng prod[].

Bước 3

Vòng lặp i từ 0 đến n-1

Bước 4

if(prod[i] > maxProd) -> maxProd = prod[i]

Bước 5

Trả về maxProd.

Chương trình minh họa

#include <iostream>
using namespace std;

long calcMaxProdSubSeq(long arr[], int n) {
    long maxProdSubSeq[n];
    for (int i = 0; i < n; i++)
        maxProdSubSeq[i] = arr[i];
    
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && maxProdSubSeq[i] < (maxProdSubSeq[j] * arr[i]))
                maxProdSubSeq[i] = maxProdSubSeq[j] * arr[i];
    
    long maxProd = -1000;
    for (int i = 0; i < n; i++) {
        if (maxProd < maxProdSubSeq[i])
            maxProd = maxProdSubSeq[i];
    }
    return maxProd;
}

int main() {
    long arr[] = {5, 4, 6, 8, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tích lớn nhất của dãy con tăng dần là " << calcMaxProdSubSeq(arr, n);
    return 0;
}

Đầu ra

Tích lớn nhất của dãy con tăng dần là 2160