Dãy con tăng dài nhất (bản khó)

Xem dạng PDF
Gửi bài giải
Điểm: 0,05 (OI)
Giới hạn thời gian: 0.3s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Bài cổ điển
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

(Giống bài LIQ) Cho một dãy gồm ~N~ số nguyên (~1~ ~\leq~ ~N~ ~\leq~ ~30000~). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

  • Dòng đầu tiên gồm số nguyên ~N~.
  • Dòng thứ hai gồm ~N~ số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Sample Input

5
2 1 4 3 5

Sample Output

3

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -2
    lenguyenminhkhang2b  đã bình luận lúc 22, Tháng 4, 2024, 13:54

    Mọi người cho mình hỏi là bài này có bản in ra dãy con không do mình học thấy có bài nhx ko có test nên mình hỏi. Mong mọi người giúp đỡ ạ. Cảm ơn mọi người nhiều ! =)) Đừng down vote mình nha


    • -1
      Le_peace  đã bình luận lúc 25, Tháng 4, 2024, 6:54

      khong ban nhe


  • -2
    thaihong7577  đã bình luận lúc 22, Tháng 4, 2024, 5:25

    Spoil!


  • 11
    YugiHackerKhongCopCode  đã bình luận lúc 21, Tháng 3, 2024, 16:47

    Spoil!

    Cách 1: Quy hoạch động + Tìm kiếm nhị phân

    Gọi mảng ~b~ : ~b_i~ là giá trị nhỏ nhất của phần tử cuối trong tất cả các dãy con tăng độ dài ~i~

    Mảng ~b~ là một dãy không giảm (~b_i \le b_{i+1}~ với mọi ~i~)

    Để tìm độ dài dãy con tăng dài nhất kết thúc tại vị trí ~a_i~, ta tìm ra vị trí ~j~ lớn nhất thoả mãn ~b_j \le a_i~, như vậy ta có thể tạo ra một dãy con tăng độ dài ~j+1~

    Do mảng ~b~ không giảm, dễ dàng tìm kiếm được vị trí ~j~ lớn nhất bằng tìm kiếm nhị phân

    Độ phức tạp ~O(n \cdot logn)~

    Link video solution: Dãy Con Tăng Dài Nhất sử dụng Tìm Kiếm Nhị Phân

    Cách 2: Quy hoạch động + Segment tree hoặc Fenwick Tree (update sau)


  • -15
    vendettas  đã bình luận lúc 17, Tháng 2, 2024, 6:07

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -10
    KiraYoshikage  đã bình luận lúc 2, Tháng 2, 2024, 15:33

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 19
    triclone_3  đã bình luận lúc 8, Tháng 11, 2023, 4:15 ← sửa 3

    Các bạn xem thì ủng hộ mình 1 down vote, mình cảm ơn! Bài này thì các bạn nên sử dụng multiset để các phần tử giống nhau sẽ không bị xoá.

    Đầu tiên nhập vào một số n

    Sau đó nhập n số vào cho hết chúng vào multiset.

    Tiếp theo dùng hàm lower_bound() để tìm m là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng với giá trị chỉ định.

    Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi. Code mẫu (C++) tại Đây


  • -21
    huynhquocluatit10  đã bình luận lúc 15, Tháng 10, 2023, 12:46

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -42
    giataino  đã bình luận lúc 14, Tháng 10, 2023, 9:26

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -28
    nhan19042007  đã bình luận lúc 12, Tháng 10, 2023, 6:53 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -79
    nthquan_1505  đã bình luận lúc 30, Tháng 3, 2023, 4:22

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -34
    maintainit  đã bình luận lúc 21, Tháng 2, 2023, 14:17

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -15
      harmxvu  đã bình luận lúc 24, Tháng 6, 2023, 13:15

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -29
    boneman23  đã bình luận lúc 8, Tháng 1, 2023, 9:47

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -18
      MaiThanh1342  đã bình luận lúc 9, Tháng 1, 2023, 8:54

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -28
    lkva2019  đã bình luận lúc 7, Tháng 1, 2023, 9:00

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -10
      maintainit  đã bình luận lúc 21, Tháng 2, 2023, 14:19

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -14
    thanh20092007  đã bình luận lúc 28, Tháng 8, 2022, 3:31

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 10
      minhducle31o  đã bình luận lúc 19, Tháng 4, 2023, 9:09

      bạn cố gắng là làm được mà. cố lên!!!


      • -4
        codelozd  đã bình luận lúc 9, Tháng 2, 2024, 8:37

        oke ban


  • -125
    modwwe  đã bình luận lúc 11, Tháng 7, 2022, 17:18

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -10
      minhducle31o  đã bình luận lúc 19, Tháng 4, 2023, 9:09

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -3
        codelozd  đã bình luận lúc 9, Tháng 2, 2024, 8:39

        oke ban


  • 22
    kennikai  đã bình luận lúc 31, Tháng 12, 2021, 5:04 ← sửa 2

    bài này làm thấm phết!