Consider an array A, possibly with repeat elements. We say that a subarray A[i...j] is strictly increasing if A[i] [i + 1] [j 1] [j].

Now consider the following problem:

Input: an array A of integers. The input array A is NOT sorted and there can be duplicates.

Output: the length of the longest strictly increasing subarray A[i...j]

For example, if A = 2,5,1,6,10,7,9 then the output is 3, since the longest strictly increasing subarray is 1,6,10.

Another example: if A = 4,3,3,1, then the output is 1, since the only increasing subarrays have a single element. e.g. A[2] is an increasing subarray of length 1.

Part 1 (20 points) Show a recursive algorithm for the above problem which runs in O(n log(n)) time. You need to write the pseudocode and state what the recurrence formula for your algorithm is.

2

NOTE: if you end up with a recursive formula that weve seen in class before, then you dont need to use a recursion tree to solve it, you can just state what the solution is. But if you end up with a new recursive formula then you need to prove that T (n) = O(n log(n)).

IMPORTANT NOTE: there exists a pretty simple fast non-recursive algo- rithms for this problem. But on this HW you must use a recursive algorithm. You will get zero points if you use a non-recursvie algorithm.

Part 2 (15 points) Give pseudocode for a recursive algorithm for the above problem that runs in O(n) time. As in part 1, you need to write the pseudocode and state what the recurrence formula for your algorithm is.

NOTE: As in Part 1, if you end up with a recursive formula that weve seen in class before, then you dont need to use a recursion tree to solve it, you can just state what the solution is. But if you end up with a new recursive formula then you need to prove that T (n) = O(n).

NOTE: once again, your algorithm must be recursive. You will get zero points if you use a non-recursive algorithm.

HINT: as we showed for the Max Profit problem in class, you will want to solve a problem LongestIncreasingSubarrayX(A) which outputs more in- formation than just the length of the longest sequence.

Grading Note: If you feel confident in your answer, you can use your solution for part 2 in part 1 as well, since an O(n) algorithm is also an O(n log(n)) algorithm. But note that Part 2 is harder, so if you dont fully confident in your approach, I recommend first getting a good solution to part 1 and then writing up a separate solution for part 2.

4 Problem 4 (35 points total) Consider an array A, posibly with repeatments. We say that a suburray Al is strictly increasing if Ad