#1. Thuật Toán Quy Hoạch Động - Bài Toán Dãy Con Tăng Dài Nhất ( LIS)

[@28tech_]

Practice problem : codeforces.com/problemsets/acmsguru/problem/99999/521 cses.fi/problemset/task/1145 leetcode.com/problems/longest-increasing-subsequence/ leetcode.com/problems/number-of-longest-increasing-subsequence/

[@skhuyen6096]

link hackerrank nx a oi

[@vietvuong9830]

Mình đóng góp code Python cho bạn nào cần thì tham khảo nhé: fi = open('lis.inp','r') fo = open('lis.out','w') n = int(fi.readline()) x = fi.readline().split() A = [int(i) for i in x] L = [1 for i in range(n)] res = 1 for i in range(1,n): for j in range(0,i): if A[i] > A[j]: L[i] = max(L[i],L[j]+1) if L[i] > res: res = L[i] fo.write(str(res)) fi.close() fo.close()

[@kiennguyen-th2tg]

n=[int(i) for i in input().split()] s=[1]*len(n) for i in range (1,len(n)): for k in range (i): if n[i]>n[k]: s[i]=max(s[i],s[k]+1) print(max(s)) tui ngắn hơn ông nè hehe

[@luisdato1712]

@@kiennguyen-th2tg Mình cũng code giống bạn nhưng khi thử bộ test 11 số [1,2,3,8,9,4,5,6,20,9,10] thì ra kết quả là 7 trong khi đáp án chính xác phải là 8 [1,2,3,4,5,6,9,10]. thật kì lạ

[@ngabcasolution5722]

Cảm ơn tác giả. rất hữu ích cho các bạn học sinh, sinh viên. Luôn ủng hộ kênh và chia sẻ cho các học trò

[@28tech_]

Em cảm ơn ạ

[@trungthanhbp]

có add thêm cái link ở dưới description rất là hữu ích :D

[@vietvuong9830]

Rất cảm ơn bạn nhé! Hướng dẫn của bạn có ý nghĩa với rất nhiều người. Góp ý nho nhỏ cho video sẽ tốt hơn đó là bạn hạn chế hơn việc nói đế OK vào cuối các câu nói nhé! Thói quen sẽ khó sửa nhưng làm được mà. Trân trọng!

[@namlequang4290]

Dễ hiểu lắm Anh, hóng phần tiếp theo. Xem các video khác vẫn chưa thông suốt lắm.

[@28tech_]

ok cố gắng lên em :D

[@htuanqn]

quá hay a ơi, e thấy chuyên đề về QHD dc nhiều người săn đón ở kênh a

[@jitan5429]

a ơi cho e hỏi là các công thức của quy hoạch động như này , a làm như nào để nghĩ ra các công thức như này vậy a ? cám ơn a nhiều

[@nguyennhunghp]

Add cho em xin link LIS độ phức tạp O(nlogn) và có in dãy với ạ. Tks add nhiều

[@HungNguyen-ur4dg]

quá tốt luôn..cảm ơn anh đã làm em thông suốt

[@28tech_]

😆😆😆

[@KietNguyen-ee7hv]

em ủng hộ series này ạ 😚

[@hoangphuc899]

cảm ơn, anh dạy kỹ lắm ạ!

[@phamtuananh2378]

a ơi sắp có vid về cách thứ hai có độ phức tạp O(nlogn) chưa ạ

[@truongtaman5663]

Cuối cùng cũng có bài toán về qhđ!

[@thanhha5251]

hay qua di em hieu quy hoach dong luon r

[@trungkiet2020]

Hay quá anh ơi, đúng cái em đang cần, ủng hộ series này 100% 😁😁

[@28tech_]

[@tranquy2547]

hay quá anh ơi, cuối cùng cũng tới phần em đau đầu nhất, ủng hộ anh

[@namquach73]

dễ hiểu, tận tình, duyệt

[@bldouyin4145]

anh giảng rất hay nhưng rất tiếc em não ngắn, sau 1 hồi xem lại thì cuối cùng cũng hiểu bài dãy con tăng hđ ntn rồi:3 cảm ơn anh ạ

[@vietvuong9830]

Riết rồi cũng hiểu cố lên em!

[@hanguyentrong8779]

chờ a mãi cuối cùng a cũng ra phần quy hoạch động

[@28tech_]

giờ lo cơm áo gạo tiền thành ra thời gian ko có rảnh như tầm năm ngoái em ạ.

[@hanguyentrong8779]

@@28tech_ Video a ra chậm nhưng mà chất lượng anh ạ vẫn ủng hộ a dài dài

[@vuongthikimhuyen1992]

Ra video truy vết đi ad ơi. Cảm ơn rất nhiều ạ

[@ucphu6269]

Anh hướng dẫn xuất ra dãy đó luôn được không ạ

[@khangnguyenviet]

đây dồi đây dồi =)) chúc a sức phẻ để ra nhiều phần về qhđ nữa nhen

[@28tech_]

[@traninhtheanh6138]

Hay quá anh lộc ơi. Em thích các video về qhđ lắm ạ

[@28tech_]

Ok chúc em học tốt.

[@decon.]

anh ơi có video lý thuyết về thuật toán quy hoạch động không ạ

[@KaiChuKo485]

Anh lên video về cách thứ hai có độ phức tạp là O(nlogn) đi ạ

[@BDCCN-NguyenVanTuan]

a có thể làm video hướng dẫn cách chung để giải quyết mấy bài quy hoạch động này đc k ạ

[@28tech_]

Phương pháp ấy hả hehe.

[@sonvuinh2366]

quá chất lượng, cảm ơn bạn

[@plee0577]

hóng mãi, quá đỉnh a ơi :33

[@leminhhai5721]

video của anh dễ hiểu quá 😁

[@28tech_]

Thank em 🤟🤟🤟

[@khoaptit]

Học anh nhiều quá em bị nhiễm chữ ok vào cuối câu nói rồi ạ huhu Hôm trước cô gọi lên giải thích code mà em ok với cô liên tục ạ :)))

[@28tech_]

Hahaha giờ ảnh bỏ rồi em

[@vuongthikimhuyen1992]

😂

[@vuongthikimhuyen1992]

Đọc bình luận cười đau bụng luôn

[@tintrung8372]

làm sao để in ra dãy đó ạ

[@hatrinh6432]

dãy con tăng dài nhất chưa có video về truy vết và phần cải tiến ah add

[@NinWuy]

Hay quá cuối cùng có series huyền thoại này :)

[@28tech_]

OK em bắt đầu thôi.

[@xienkhum9980]

Anh có vid cải tiến thuật toán chưa ạ

[@VanThanh-cb8uk]

3 năm trước có video này thì zui r :vv

[@youaresocute2002]

cuối cùng cũng có quy hoạch động rồi hehe

[@28tech_]

🤟

[@khavovan8201]

Sắp 10k rùi anh ơi🥰🥰🥰🥰

[@28tech_]

Haha, hồi em sub nó mới được có 80 90 sub.

[@khavovan8201]

@@28tech_ fan cứng mà anh hehe

[@tinnhiem8527]

ra thêm các bài tập CTDL stack queue đi anh

[@28tech_]

Thế thì vô vàn lắm hehe.

[@mitvuong1856]

sắp có bài lis nlogn chưa a

[@28tech_]

Chưa có em ạ

[@ngocthaovu]

video hay quá ạ

[@28tech_]

Cảm ơn em chúc em học tốt nhé

[@ngocthaovu]

@@28tech_ mong anh ra nhiều video hơn nữa ạ

[@funnymeme6981]

làm thế nào để in ra tất cả các dãy con không giảm vậy anh

[@miningcraft897]

Anh ơi cho em xin cái bài mà anh làm trong video ấy, ở hackkerrank hay sao ấy ạ

[@28tech_]

Này Ko còn rồi bạn ạ

[@miningcraft897]

@@28tech_ Dạ vâng ạ

[@miningcraft897]

@@28tech_ Vậy còn mấy bài nào liên quan cũng trên hackerrank ko ạ?

[@DaThuFlorida]

Đi thi xài auto, themis có chấm không anh.

[@animekay3405]

Này o(n)^2 hả a có ý tưởng nào dưới nó k ạ

[@thanhbinhnguyen5943]

quá hay anh ơi ~~~~

[@28tech_]

🤪🤪🤪🤪

[@iluminatibox9949]

thuật toán này là sliding window đúng không nhỉ?

[@28tech_]

Ko phải

[@kienbuitrung7555]

#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(nullptr); mấy cái dòng này là cái dòng gì vậy anh, em thấy ngta lập trình hay gắn như này nên em cx bắt chước theo chứ không thực sự biết tác dụng của nó là gì. Mong anh giải thích vs ạ, vs lại em không biết run code kiểu s khi có mấy dòng này nữa

[@mitvuong1856]

ios_base::sync_with_stdio(false); Dùng cin/cout bình thường sẽ bất lợi về thời gian do phải đồng bộ với stdin/stdout (vì lí do lịch sử nên phải có đồng bộ này). Gặp bài I/O nhiều phải có câu này, nếu I/O ít thì không đáng kể. cin.tie(0); để ngăn sự đồng bộ giữa cin và cout: chỉ khi cout xuất ra hết thì cin mới nhập vào (và ngược lại). Việc đồng bộ này chỉ có chương trình tương tác mới cần.

[@Lunguyen08]

Hồi lớp 8 cô dạy để thi hsg tin bài này mà ko hiểu chi hết, bây giờ lên lớp 10 nghe anh giảng mới thông😂😂😂, mà cho em hỏi cài đặt lis vs độ phức tạp là O(nlogn) là video nào vậy anh😢😢😢

[@zapdown6116]

hh trùng hợp v, hồi lp9 mình cx hc thuộc mấy bài qhd này vào phòng thi😂😂😂

[@ucNguyen-iv8iu]

anh ơi ra vid in dãy ra chưa ạ

[@nvnhuquynh4505]

có link nộp bài k ạ

[@catorlife]

cho e hỏi trong CP thì nên xài mảng bình thường hay vector vậy a?

[@28tech_]

Em dùng cái nào cũng được, như nhau cả mà

[@truongminhnhut4993]

Nếu mà làm dãy con giảm thì sao vậy ad

[@ahardworkingbee]

Dễ quá bạn ei ^^

[@phamhonganh3708]

anh cho em xin link bài này trên hackerrank đc ko ạ

[@thuanmevan5683]

Anh nói to hơn ạ, em mong anh

[@truongtra1183]

Nếu họ ko ra đề là 'dãy con liên tiếp ' thì mình tìm các phần tử cách nhau đúng ko ạ ?

[@nhndO_o]

anh làm phần truy vết đi ạ

[@thiemhoang3015]

làm sao để in cả dãy ra vậy anh

[@tienato2042]

có phần giải bài này cho java không ạ

[@28tech_]

Jca em code tương tự thôi

[@cuongnguyenmanh5251]

Làm sao để nó hiện tiếng Việt như thế kia vậy anh ơi?

[@ducmih2203]

bài này dùng lower_bound nhanh hơn anh ạ

[@quyle2185]

Ok nha anh

[@hoangdev2305]

với n = 10^5 thì có thuật toán nào tối ưu k ạ

[@28tech_]

Có em nhé có thể kết hợp binary search, đợi video sau nhé

[@datgameon2656]

a ơi, cải tiến thuật toán đc ko a :))

[@AnNguyen-mf7zb]

ko có phần truy vết à anh

[@NguyễnLong-o1t]

em cảm ơn anh

[@luukhai3886]

thay vì cho L[i] = max(L[i], L[j] + 1) thì sao mình không cho L[i]++ luôn nhỉ? cũng là xét a[i] > a[j] mà int main() { int n; cin >> n; vector arr(n); for (int i = 0; i < n; i++) cin >> arr[i]; vector L(n,1); int max_val = 0; for (int i = 1; i arr[j]) L[i] ++; } max_val = max(max_val, L[i]); } cout

[@IamNix]

ChatGPT: The line L[i] = max(L[i], L[j] + 1) is used to update the length of the longest increasing subsequence that ends at index i. The reason for using max(L[i], L[j] + 1) instead of just L[j] + 1 is that there may be multiple increasing subsequences that could potentially end at index i, and we want to choose the one that results in the longest overall subsequence. Consider the following input array: Copy code 3 4 1 5 2 Initially, the array L is set to all ones: Copy code 1 1 1 1 1 When we process arr[2] (which is 1), we compare it to all previous elements in the array to see if it could be part of a longer increasing subsequence. In this case, it cannot be part of any increasing subsequence longer than 1, because it is smaller than all previous elements. So L[2] remains at 1. When we process arr[3] (which is 5), we compare it to all previous elements in the array to see if it could be part of a longer increasing subsequence. It is larger than arr[0], arr[1], and arr[2], so it can be part of a longer increasing subsequence. In this case, the longest increasing subsequence that ends at index 3 is {3, 4, 5}. To update L[3], we add 1 to the length of the longest increasing subsequence that ends at j=1 (which is {3, 4}), since arr[3] is larger than arr[1]. We get L[3] = L[1] + 1 = 2. When we process arr[4] (which is 2), we compare it to all previous elements in the array to see if it could be part of a longer increasing subsequence. It is smaller than arr[0], arr[1], arr[2], and arr[3], so it cannot be part of any increasing subsequence longer than 1. So L[4] remains at 1. The resulting L array is: Copy code 1 1 1 2 1 The length of the longest increasing subsequence is 2, which is correctly found by the algorithm. If we had used L[i] = L[j] + 1 instead of L[i] = max(L[i], L[j] + 1), we would have missed the longer subsequence {3, 4, 5} and incorrectly calculated the LIS to be 1.

[@luukhai3886]

@@IamNix tóm lại giải thích bằng tiếng việt đi

[@IamNix]

@@luukhai3886 là bạn hiểu sai vấn đề. Nếu làm như vậy. Bạn luôn giả định phần tử áp chót luôn được chọn.

[@itnhalam]

anh ơi có phần giảm độ phức tạp của bài này chưa ạ

[@28tech_]

chưa có em ơi.

[@vietnamesegeneral7793]

chặt nhị phân

[@NMnhSon]

viết code mà không chuyển unikey là sao??

[@28tech_]

@@NMnhSon nó là quyền của mình, bạn có quyền gì bảo mình phỉ chuyển hay ko?

[@KienNguyen-mo3we]

tym đầu ạ

[@28tech_]

😁😁😁

[@kuripuri4670]

Mình chx hiểu tại sao L[i]=max(L[i],L[j]+1), ai đó vô thông não cái

[@hoangduonghn]

trời ơi, cứ ô kê, ô kê, khó học quá

[@28tech_]

Oke em có thể sang kênh khác học nha

[@hoangduonghn]

@@28tech_ Vầng anh Xin lỗi anh, em không có ý chê bài giảng cảu anh, vì em mới đang tập tành, đó có thể là do vấn đề tâm lý của em, việc lặp từ quá gây rối loạn tiếp thu, nhưng nó cũng là một vấn đề của anh

[@evuongnguyen5281]

khó hiểu quá

[@anhung9351]

:)))

[@28tech_]

[@nxsang1611]

Lsao để in dãy con đó ra v ạ