Question:
Take a list of integers. Can you find a longest non-decreasing subsequence of the list?
If the list were sorted, the problem would be easy enough. However the list is more likely to be something like this:
| 37 | 93 | 0 | 23 | 79 | 65 | 49 | 81 | 67 | 8 | 32 | 29 | 96 | 76 | 15 | 9 | 51 | 14 | 29 | 69 |
Trying to solve #1:
After thinking for a bit, i have decided to try to solve this using Java:
public static int[] longestSubSeq(int[] List){
ArrayList<ArrayList> subSeq = new ArrayList();
ArrayList<Integer> temp = new ArrayList();
//Goes through each element of the list
for (int start = 0; start < List.length; start++){
ArrayList<Integer> toCheck = new ArrayList();
//Copies all elements after the current index
for (int begin = start + 1; begin < List.length - start; begin ++){
toCheck.add(List[begin]);
}
int currentBiggest = List[start];
//Finds all the subsequences possible that is non-decreasing
//and adds it to subSeq
while (toCheck.size() != 0){
temp.add(List[start]);
for (int number : toCheck){
if (number >= currentBiggest){
temp.add(number);
currentBiggest = number;
}
}
toCheck.remove(0);
subSeq.add(new ArrayList(temp));
temp.removeAll(temp);
currentBiggest = List[start];
}
}
int intLongest = 0;
ArrayList<Integer> lstLongest = new ArrayList();
System.out.println(subSeq.size());
for (ArrayList<Integer>subSequence : subSeq){
if (subSequence.size() > intLongest){
intLongest = subSequence.size();
lstLongest = new ArrayList(subSequence);
}
}
int size = lstLongest.size();
int[] list = new int [size];
int count = 0;
for (int number : lstLongest){
list[count] = number;
count ++;
}
return list;
}
I then thought about and realized that the code would have missed some combinations. It worked with the current list and gave me a list of length 5, but it might not have worked with another. So i went on to trying a new method.
Trying to Solve #2:
I wanted to create and array of lists with all the possible combinations of the given list. So if i had {1,3,2}
I would result in {{1}, {3}, {2}, {1,3}, {1,2}, {3,2}, {1,3,2}}
Then i would check if each and every one of the list is non decreasing. If it is, pop it out from the list.
The resulting array of lists will become {{1}, {3}, {2}, {1,3}, {1,2}}
Then we will find the list with the longest length inside the array and that would be the longest non decreasing list.
The longest list will be either {1,3} or {1,2} depending on the code.
Now that there's 30 minutes left, and it will take too long to code, so i shall leave the solution as that. This solution might not be the most efficient one, but it should work.
