481 - What Goes Up

[jddantes]

It's RTE with either.

[brianfry713]

With C++11, you're getting TLE.
http://en.wikipedia.org/wiki/Longest_in ... ubsequence
Use binary search.

[just_yousef]

brianfry713
can you please give links to other problems that needs to be solved with binary search

[brianfry713]

http://uhunt.felix-halim.net
Competitive Programming Exercises
Chapter 3. Problem Solving Paradigms
Divide and Conquer

[Shahidul.CSE]

I solved it in O(nlogk)

[brianfry713]

http://en.wikipedia.org/wiki/Longest_in ... ubsequence
Use binary search.

[anando_du]

O(n^2) solution will get TLE so must use O(nlogk) solution.

[cunbidun]

someone help me with my code plz
i dont understand why it cause run time error

Code: Select all

#include <stdio.h>
#include<string.h>
#include<math.h>


int main() {
  // freopen("lis.inp","r",stdin);
    int pred[1000],i,n,j,max=0,a[1000],s=0,l[1000],dmax,j0,x[1000],k,m,sa;
    i=1;
    while(scanf("%d",&sa)!=EOF)
    {
       a[i]=sa;
       i++;
    }
    n=i-1;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    l[1]=1;
    dmax=1;
    pred[1]=-1;
    pred[0]=-1;
for(i=2;i<=n;i++)
{
    max=0;
    j0=0;

    for(j=i-1;j>=1;j--)
        if(a[i]>a[j] && l[j]>max)
                {
                    max=l[j];
                    j0=j;
                }
        l[i]=max+1;
        pred[i]=j0;
        if(l[i]>=dmax) {dmax=l[i];k=i;}
}

    printf("%d\n",dmax);

       printf("-\n");


    m=0;
    while(k!=-1)
        {
            m++;
            x[m]=a[k];
            k=pred[k];
            if(k==0) break;
        }
    for(i=m;i>1;i--)
        printf("%d\n",x[i]);
        printf("%d\n",x[1]);

}