I was trying a problem on SPOJ,in which we have to simply find the Length of Longest Increasing Sub-sequence of the given Array A.
I had solved this problem using a dynamic programming O(n^2)algorithm and the solution got accepted..Here is the code,that got Accepted:
void LIS(int *A,int A_Length)
A simple way of finding the longest increasing subsequence is
to use the Longest Common Subsequence (Dynamic Programming) algorithm.
Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
Use Longest Common Subsequence on with A and B. O(n2) time.
//This function Finds the Longest common subsequce of Array A[1,2,3...,N] and B[1,2,3...,N]
void LIS(int N)
sort((B+1),(B+1)+N);//STL SORT sort from index 1 to N of Array B.
The Second Method is correct, but can't be applied to this problem directly. That's because the numbers in the sequence are not guaranteed to be unique in this SPOJ problem, and the target is to find a strict increasing subsequence, while Your Second Method's output is non-decreasing subsequence here. Demonstrating on a simple test case
[1,2,2,3] will help you find the difference.
This solution is also simple: just remove the duplicated elements after sorting.