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, 30) is 5 and one such sub-array is 5, 10, 13, 19, 303. Note you may have multiple solutions for this case. Use dynamic programming to solve this problem. Answer the following questions a) What is the optimal substructure of this problem? b) Show the pseudo code of your solution and its complexity in terms of asymptotic analysis c) Use two examples to demonstrate how your approach works. In cases where there are multiple longest sub-arrays, you just need to show one of them d) How can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal solution