Advertisement
eynizadeMurad

Dynamic Programming - Largest Increasing Subsequence

Mar 28th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m[1001],len[1001],ans;
  4. int main() {
  5.     cin>>n;
  6.     for (int i=1;i<=n;i++) 
  7.         cin>>m[i];
  8.     for (int i=1;i<=n;i++) {
  9.         len[i] = 1;
  10.         for (int j=1;j<i;j++) {
  11.             if (m[i] > m[j]) {
  12.                 len[i] = max(len[j]+1,len[i]);
  13.                 ans = max(ans,len[i]);
  14.             }
  15.         }
  16.     }
  17.     cout<<ans<<endl;
  18.     return 0;
  19. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement