Skip to content

Instantly share code, notes, and snippets.

@rickyzhang-cn

rickyzhang-cn/lis.cpp

Created May 8, 2015 07:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save rickyzhang-cn/dc6685511839c0b413e7 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save rickyzhang-cn/dc6685511839c0b413e7 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. rickyzhang-cn created this gist May 8, 2015.
    23 changes: 23 additions & 0 deletions lis.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,23 @@
    #include <iostream>
    using namespace std;

    int lis(int A[], int n){
    int *d = new int[n];
    int len = 1;
    for(int i=0; i<n; ++i){
    d[i] = 1;
    for(int j=0; j<i; ++j)
    if(A[j]<=A[i] && d[j]+1>d[i])
    d[i] = d[j] + 1;
    if(d[i]>len) len = d[i];
    }
    delete[] d;
    return len;
    }
    int main(){
    int A[] = {
    5, 3, 4, 8, 6, 7
    };
    cout<<lis(A, 6)<<endl;
    return 0;
    }