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/
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!
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()
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
@@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ạ
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😢😢😢
#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
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.
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
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.
@@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
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/
link hackerrank nx a oi
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ò
Em cảm ơn ạ
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.
ok cố gắng lên em :D
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!
có add thêm cái link ở dưới description rất là hữu ích :D
Hay quá anh ơi, đúng cái em đang cần, ủng hộ series này 100% 😁😁
quá hay a ơi, e thấy chuyên đề về QHD dc nhiều người săn đón ở kênh a
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()
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
@@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ạ
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 ạ
Riết rồi cũng hiểu cố lên em!
hay quá anh ơi, cuối cùng cũng tới phần em đau đầu nhất, ủng hộ anh
em ủng hộ series này ạ 😚
quá tốt luôn..cảm ơn anh đã làm em thông suốt
😆😆😆
cảm ơn, anh dạy kỹ lắm ạ!
Hay quá anh lộc ơi. Em thích các video về qhđ lắm ạ
Ok chúc em học tốt.
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
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 ạ :)))
Hahaha giờ ảnh bỏ rồi em
😂
Đọc bình luận cười đau bụng luôn
đây dồi đây dồi =)) chúc a sức phẻ để ra nhiều phần về qhđ nữa nhen
chờ a mãi cuối cùng a cũng ra phần quy hoạch động
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 ạ.
@@28tech_ Video a ra chậm nhưng mà chất lượng anh ạ
vẫn ủng hộ a dài dài
hóng mãi, quá đỉnh a ơi :33
dễ hiểu, tận tình, duyệt
quá chất lượng, cảm ơn bạn
hay qua di em hieu quy hoach dong luon r
Add cho em xin link LIS độ phức tạp O(nlogn) và có in dãy với ạ. Tks add nhiều
video của anh dễ hiểu quá 😁
Thank em 🤟🤟🤟
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😢😢😢
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😂😂😂
Hay quá cuối cùng có series huyền thoại này :)
OK em bắt đầu thôi.
Cuối cùng cũng có bài toán về qhđ!
a ơi sắp có vid về cách thứ hai có độ phức tạp O(nlogn) chưa ạ
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 ạ
Phương pháp ấy hả hehe.
Anh lên video về cách thứ hai
có độ phức tạp là O(nlogn) đi ạ
anh ơi có video lý thuyết về thuật toán quy hoạch động không ạ
Ra video truy vết đi ad ơi. Cảm ơn rất nhiều ạ
Sắp 10k rùi anh ơi🥰🥰🥰🥰
Haha, hồi em sub nó mới được có 80 90 sub.
@@28tech_ fan cứng mà anh hehe
Anh hướng dẫn xuất ra dãy đó luôn được không ạ
video hay quá ạ
Cảm ơn em chúc em học tốt nhé
@@28tech_ mong anh ra nhiều video hơn nữa ạ
cuối cùng cũng có quy hoạch động rồi hehe
🤟
Này o(n)^2 hả a có ý tưởng nào dưới nó k ạ
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
quá hay anh ơi ~~~~
🤪🤪🤪🤪
sắp có bài lis nlogn chưa a
Chưa có em ạ
ra thêm các bài tập CTDL stack queue đi anh
Thế thì vô vàn lắm hehe.
Đi thi xài auto, themis có chấm không anh.
em cảm ơn anh
Anh ơi cho em xin cái bài mà anh làm trong video ấy, ở hackkerrank hay sao ấy ạ
Này Ko còn rồi bạn ạ
@@28tech_ Dạ vâng ạ
@@28tech_ Vậy còn mấy bài nào liên quan cũng trên hackerrank ko ạ?
3 năm trước có video này thì zui r :vv
Anh có vid cải tiến thuật toán chưa ạ
cho e hỏi trong CP thì nên xài mảng bình thường hay vector vậy a?
Em dùng cái nào cũng được, như nhau cả mà
Ok nha anh
#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
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.
làm thế nào để in ra tất cả các dãy con không giảm vậy anh
Dễ quá bạn ei
^^
thuật toán này là sliding window đúng không nhỉ?
Ko phải
tym đầu ạ
😁😁😁
anh sử dụng phần mềm code gì vậy ạ
Sublime text nhé em
@@28tech_ dạ anh
a ơi, cải tiến thuật toán đc ko a :))
làm sao để in ra dãy đó ạ
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 ạ ?
anh cho em xin link bài này trên hackerrank đc ko ạ
anh ơi ra vid in dãy ra chưa ạ
Nếu mà làm dãy con giảm thì sao vậy ad
có link nộp bài k ạ
với n = 10^5 thì có thuật toán nào tối ưu k ạ
Có em nhé có thể kết hợp binary search, đợi video sau nhé
Anh nói to hơn ạ, em mong anh
có phần giải bài này cho java không ạ
Jca em code tương tự thôi
bài này dùng lower_bound nhanh hơn anh ạ
Làm sao để nó hiện tiếng Việt như thế kia vậy anh ơi?
anh ơi có phần giảm độ phức tạp của bài này chưa ạ
chưa có em ơi.
chặt nhị phân
ko có phần truy vết à anh
anh làm phần truy vết đi ạ
làm sao để in cả dãy ra vậy anh
viết code mà không chuyển unikey là sao??
@@NMnhSon nó là quyền của mình, bạn có quyền gì bảo mình phỉ chuyển hay ko?
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
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.
@@IamNix tóm lại giải thích bằng tiếng việt đi
@@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.
Mình chx hiểu tại sao L[i]=max(L[i],L[j]+1), ai đó vô thông não cái
trời ơi, cứ ô kê, ô kê, khó học quá
Oke em có thể sang kênh khác học nha
@@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
khó hiểu quá
:)))
Lsao để in dãy con đó ra v ạ