Created
May 19, 2024 10:20
-
-
Save jason810496/5e6ffe0f7e512b8163ca1d7ff7f9079d to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<iostream> | |
| #include<vector> | |
| #include<algorithm> | |
| #include<utility> | |
| #define ll long long | |
| #define OAO cin.tie(0);ios_base::sync_with_stdio(0); | |
| #define F first | |
| #define S second | |
| #define PB push_back | |
| #define all(x) x.begin(),x.end() | |
| using namespace std; | |
| typedef pair<int,int> pii; | |
| typedef vector<int> vi; | |
| typedef vector< vector<int> > vvi; | |
| typedef vector< pair<int,int> > vpii; | |
| const int MAX_N = 1e5; | |
| const int INF = 1e9; | |
| const int MOD = 1e9+7; | |
| void longest_increasing_subsequence_n_square(vi &a){ | |
| int n = a.size(); | |
| vi dp(n,1); | |
| for(int i=1;i<n;i++){ | |
| for(int j=0;j<i;j++){ | |
| if( a[i] > a[j] ){ | |
| dp[i] = max(dp[i],dp[j]+1); | |
| } | |
| } | |
| } | |
| cout<<*max_element(all(dp))<<"\n"; | |
| } | |
| void longest_increasing_subsequence_n_log_n(vi &a){ | |
| int n = a.size(); | |
| vi dp; | |
| for(int i=0;i<n;i++){ | |
| auto it = lower_bound(all(dp),a[i]); | |
| if( it == dp.end() ){ | |
| dp.PB(a[i]); | |
| } | |
| else{ | |
| *it = a[i]; | |
| } | |
| } | |
| cout<<dp.size()<<"\n"; | |
| } | |
| signed main(){ | |
| OAO | |
| vi a = {10,9,2,5,3,7,101,18}; | |
| longest_increasing_subsequence_n_square(a); | |
| longest_increasing_subsequence_n_log_n(a); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment