LIS - Dãy con tăng dài nhất

Xem dạng PDF
Gửi bài giải
Điểm: 3,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
codey
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
  • Cho một dãy số nguyên a, hãy tìm độ lớn của dãy con tăng dài nhất của dãy này

Input

  • Dòng đầu tiên chứa một số nguyên n, là độ lớn của dãy số (1 < n < ~10^6~)
  • n dòng tiếp theo, mỗi dòng chứa một số nguyên của dãy a ( a < a[i] < ~10^5~)

Output

  • Độ lớn của dãy con tăng dài nhất của a

Sample

Input #1
5
2
7
4
3
8
Output #1
3

Hint

  • Với test trên, ta có thể nhận thấy dãy con tăng dài nhất là: [2,7,8] với độ lớn của dãy là 3

Bình luận

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


  • 0
    dainghiajustiin  đã bình luận lúc 8, Tháng 6, 2025, 16:11

    Code Python BIT bài này của mình (LƯU Ý: CODE KHÔNG AC, CHỈ MANG TÍNH CHẤT THAM KHẢO).

    BIT = [0] * 100001
arr = [0] * 1000001
nSize = 0

def max(a, b):
   if(a > b):
       return a
   return b

def lowbit(index):
   return (index & (-index))

def get(index):
   result = 0
   while(index > 0):
       result = max(result, BIT[index])
       index -= lowbit(index)
   return result

def add(index, length):
   while(index <= 100000):
       BIT[index] = max(BIT[index], length)
       index += lowbit(index)

nSize = int(input())

for i in range(1, nSize + 1):
   arr[i] = int(input())

for i in range(1, nSize + 1):
   curLength = get(arr[i] - 1) + 1
   add(arr[i], curLength)

print(get(100000))

  • -1
    buiminhkhoi  đã bình luận lúc 25, Tháng 2, 2025, 14:55 ← chỉnh sửa

    con gà vẩu =))))))))))


  • 16
    tri_88  đã bình luận lúc 8, Tháng 1, 2024, 8:59 ← chỉnh sửa

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

    Khi nào n > 0.

    Thì nhập vào 1 số a.

    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 a

    Sau khi dùng hàm lower_bound() xong các bạn phải cộng thêm 1 vì vị trí m trong multiset thực tế là m+1.

    Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi.

    (Nếu như m != multiset.end() thì xoá đi để tìm 1 vị trí khác thoả mãn)

    Thì kích thước của multiset sẽ là kết quả của bài.

    Code mẫu (C++) tại Đây


    • 0
      lek176234  đã bình luận lúc 4, Tháng 3, 2024, 12:23

      Ụ anh ơi nếu em nhập 7 và 2 3 4 5 1 6 7 thì nó in ra 6 chứ k phải 7


      • 1
        lek176234  đã bình luận lúc 4, Tháng 3, 2024, 12:26

        À em đọc nhầm đề :>


    • -2
      haidang3004  đã bình luận lúc 8, Tháng 1, 2024, 15:23

      hay bạn ơi