Q:

How to find the longest increasing subsequence?

I'm trying to use a code to print the  longest increasing subsequence,the code works but it doesn't print the right longest increasing subseqquence .

for example if the input was :3,5,11,8,4,7,1,2,10,12,9,6
The output is : [1, 2, 6, 9, 12]
my desired output is : 3,4,7,10,12
I've debugging the way of inserting and printing the arraylist and its correct , I believe that there is something wrond here,why was is wrong?why it changes the order of numbers!?
public static ArrayList<Integer> lengthOfsequance(ArrayList<Integer> nums) {

    if (nums == null || nums.size() == 0)
        return null;
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int num : nums) 
    {
        if (list.size() == 0 || num > list.get(list.size() - 1)) 
            list.add(num);
        else
        {
            int i = 0;
            int j = list.size() - 1;
            while (i < j) 
            {
                int mid = (i + j) / 2;
                if (list.get(mid) < num) 
                    i = mid + 1;
                else
                    j = mid;
            }
           list.set(j, num);
        }
    }
    return list;
}

A:

Your approach can't work. You are using one list to collect the longest sequence. But your input sequence can have multiple increasing sequences. Maybe one that goes from index 0 to 5; and another one that goes from index 10 to 20. 
In other words; you need a different strategy; and the "straight forward" approach is something like:

iterate the input list, to "collect" all increasing sequences (in other words: that would be a List of Lists).
Afterwards, you look into that List of Lists to find the max-length one

Of course, this can then be further optimized - you don't need to remember all increasing sequences, you just have to remember about the "longest completed" sequence that you saw before. 
But as said: the first, naive implementation would be to simply identify all "increasing + complete" sequences in the input list. And then you work  your way from there.
( as I assume this is some kind of homework project I am only giving guiding ideas, not source code. Implementation is left as exercise to the reader )
Edit: to address the comment "how to avoid remembering 'equal' sequences".
Assume your input is this sequence: 1,2,3,0,1,2,3,4,1,2,3
When you look for increasing sequences in there, you should find:
(1, 2, 3) and (0, 1, 2, 3, 4), and (1, 2, 3)
You are correct: if you represent the above tuples as List<Integer>; then "correct" code would collect three lists; where the first and third would be equal (because they contain the very same numbers).
And when you store those lists within a List<List<Integer>> then, yes, your code would have to account for duplicates. One way of avoiding that could be to use a Set<List<Integer>> instead - because the Set makes sure by nature that all entries stored within that collection are not equal. In other words: when you add two lists with the same content to a Set object, then, in the end, the Set will only contain one of those two lists. (one thing to be aware of - when you use a HashSet here, then the order of add operations is lost ).
Finally: instead of using Set<List<Integer>> you could also you use a Map<Integer, Integer> with "key" being the length of a sequence; and  "value" being the first index within the input list.
In other words: instead of remembering the whole sequence, you can as well just remember at which position a sequence starts, and how many elements that sequence has. 
Long story short: there are many many different ways to solve this puzzle, using all kinds of data structures and looping/counting mechanisms. So, don't stop with the first working version, but keep playing.

