Suppose you are given an array of n integers a1, a2, ..., an. You need to find out the length of its longest sub-array (not necessarily contiguous) such that all elements in the sub-array are sorted in non-decreasing order. For example, the length of longest sub-array for { 5, 10, 9, 13, 12, 25, 19, 70, 80 } is 6 and one such sub-array is {5, 10, 13, 19, 70, 80}. Note you may have multiple solutions for this case. Use dynamic programming to solve this problem. Your solution need to show:
1) the optimal substructure;
2) the pseudo code of your solution and its complexity; and
3) a few examples how your approach works. In cases where there are multiple longest sub-arrays, you just need to show one of them.