I was learning the fundamentals of dynamic programming and came over to the question of finding the Longest Increasing Subsequence in an array. Before looking up the DP solution, I decided to code it myself and came up with the following algorithm, the complete code to which can be found here.
The idea is to create a List Array to store all the increasing subsequences, and store the corresponding max value of each subsequence for faster comparisons.
private void findLIS(int[] inputArr) {
List[] listOfSubs = new ArrayList[inputArr.length]; //Max different subsequences in an array would be N
//To store the max value of each of the subsequences found yet
List<Integer> maxValList = new ArrayList<Integer>();
listOfSubs[0] = new ArrayList<Integer>();
listOfSubs[0].add(inputArr[0]); //Add the first element of the array to the list
maxValList.add(inputArr[0]);
for (int i=1;i<inputArr.length;i++) {
boolean flag = false;
int iter=0;
//Compare inputArr[i] with the maxVal of each subsequence
for (int j=0; j<maxValList.size(); j++) {
if (inputArr[i]>maxValList.get(j)) {
maxValList.set(j, inputArr[i]); //Update the maxVal in the corresponding position in the list
listOfSubs[j].add(inputArr[i]);
flag = true;
}
iter = j;
}
//If inputArr[i] is not greater than any previous values add it to a new list
if (!flag) {
maxValList.add(inputArr[i]);
listOfSubs[iter+1] = new ArrayList<Integer>();
listOfSubs[iter+1].add(inputArr[i]);
}
}
//Finding the maximum length subsequence among all the subsequences
int max=0, iter=0, index=0;
for (List<Integer> lst : listOfSubs) {
if (lst!=null && lst.size() > max) {
max = lst.size();
index=iter;
}
iter++;
}
//Print the longest increasing subsequence found
System.out.println("The Longest Increasing Subsequence is of length " + listOfSubs[index].size() +
" and is as follows:");
for (int i=0;i<listOfSubs[index].size();i++) {
System.out.print(listOfSubs[index].get(i) + " ");
}
}
The code runs in O(n^2) time and works perfectly for small/medium sized inputs. However, when I try running the code against some of the online practice portals (like HackerRank), I get both TLE (Time Limit Exceeded Errors) and Wrong Answer. I understand the TLE errors, as the efficient solution is a DP O(nlogn) solution, but I'm confused about the wrong answers generated by this algorithm. Since, the inputs for such cases are too big (~10000), I'm unable to manually verify the where the solution goes wrong.
The complete code plus the output to one of the data sets can be found here. The correct answer should be 195 as reported by HackerRank.
Why is this an off-topic question?I consider it borderline: essential parts are expected in the question to keep it self-contained when links go stale. You describe what you do to solve the problem, but not what the result is/why that solves (should solve) the problem. I'm missing at least the WA output (20). (I'm surprised at the output format you use/show.) – greybeard