I have learned LIS with DP from MAXImal.But can not print the sequence. it just shows the longest length. if I want to print the sequence then what the modifies should I do.

http://e-maxx.ru/algo/longest_increasing_subseq_log

Here the code.

int main() { int n;

cin>>n;

int dp[n+1],arr[n];

dp[0] = -INF;

for(int i=0;i<n;i++){

    scanf("%d",&arr[i]);

    dp[i+1]=INF;

}

for(int i=0;i<n;i++){

   int j=upper_bound(dp,dp+n+1,arr[i])-dp;

   if(dp[j-1] < arr[i] && arr[i] < dp[j]) dp[j] = arr[i];

}

for(int i: dp) cout<<i<<endl;

return 0;

}

Sorry for my poor English.