Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Cho một dãy số nguyên gồm phần tử . Biết rằng dãy con tăng đơn điệu là dãy thỏa mãn và .…

  1. User

    Cho một dãy số nguyên gồm phần tử .

    Biết rằng dãy con tăng đơn điệu là dãy thỏa mãn và . Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

    Input Dòng gồm số nguyên là số . Dòng thứ ghi số nguyên . Output Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

    Sample Input Copy 6 1 2 5 4 6 2

  2. Assistant

    Với dãy số đã cho, ta có thể sử dụng thuật toán tăng dần (dynamic programming) để tìm dãy con tăng đơn điệu dài nhất.

    Xây dựng một mảng dp có độ dài bằng với số phần tử của dãy gốc. Gán mỗi phần tử của mảng dp bằng 1, đại diện cho độ dài của dãy con tăng đơn điệu tại vị trí tương ứng với vị trí i của dãy gốc.

    Duyệt qua từng phần tử của dãy gốc từ vị trí 1 đến n, ta cập nhật giá trị dp[i] như sau:

    • Với mỗi phần tử j từ vị trí 0 đến i-1, nếu arr[i] > arr[j] và dp[i] < dp[j] + 1, ta cập nhật dp[i] = dp[j] + 1. Điều này đồng nghĩa với việc tìm thấy dãy con tăng mà có độ dài tăng thêm 1 so với dãy con tăng tại vị trí j.

    Cuối cùng, ta tìm giá trị lớn nhất trong mảng dp và ghi ra đáp án là giá trị lớn nhất đó.

    Ví dụ:

    Input:
    6
    1 2 5 4 6 2
    
    Output:
    3
    

    Giải thích: Dãy con tăng đơn điệu dài nhất của dãy số là 1 2 5.

  3. User

    c++ 17

  4. Assistant

    Dưới đây là một chương trình C++ để giải quyết bài toán này sử dụng thuật toán tăng dần:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    int main() {
        int n;
        std::cin >> n;
        
        std::vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> arr[i];
        }
        
        std::vector<int> dp(n, 1);
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        
        int max_len = *std::max_element(dp.begin(), dp.end());
        
        std::cout << max_len << std::endl;
        
        return 0;
    }
    

    Chúng ta sẽ khởi tạo một vector dp có kích thước bằng với n để lưu trữ độ dài của dãy con tăng đơn điệu tại mỗi vị trí của dãy gốc. Sau đó, chúng ta duyệt qua từng phần tử của dãy gốc và cập nhật các giá trị trong vector dp theo quy tắc đã mô tả ở trên. Cuối cùng, ta tìm giá trị lớn nhất trong vector dp và in ra kết quả.