Register | Login

Solutions of Longest increasing subsequence

Select solution language All Tiếng Việt English Other

Write solution here.

---

phphongyd    Created at    0 likes

Cho dãy số A = a[1], a[2], ..., a[n]. Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Yêu cầu: Tìm dãy con đơn điệu tăng dài nhất của A Hướng dẫn: Gọi L[i] là độ dài dãy con đơn điệu tăng dài nhất của dãy a[1], a[2],...,a[i] và kết thúc bằng a[i] (Cần tìm Max(L[i]) Ta có: L[i] = 1 với mọi i = 1 -> n L[i] = max(L[k] với mọi k = 1->i - 1 thỏa mãn a[k]<a[i]) + 1 Code C++; ``` #include <bits/stdc++.h> const int N=1e4; using namespace std; long long n,a[N+5]; int main() { cin>>n; for(int i=0;i<n;i++)cin>>a[i]; vector<int>l(n,1); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(a[i]>a[j]){ l[i]=max(l[i],l[j]+1); } } }cout<<*max_element(l.begin(),l.end()); return 0; } ```