2) Suppose a student wrote the below code for the previous question (Maximum Subsequence Sum problem (MSS)). What is the running time of this algorithm?

3) Suppose another student who is a better programmer wrote the below code for Maximum Subsequence Sum problem (MSS). What is the running time for this algorithm?

4) Suppose another student decides to solve the Maximum Subsequence Sum problem (MSS) using divide and conquer technique:

Divide: Divide the array into two halves.

Conqure: Recursively find MSS of the two sub-arrays, each of size n/2,

Combine: Now in order to combine the sub-arrays you need to know that MSS can lie in one of the following places:

1- Entirely in the left sub-array

2- Entirely in the right sub-array

3- Intersects both halves:

(We can easily find a maximum sub-array crossing the midpoint in time linear in the size of the sub-array. This problem is not a smaller instance of our original problem, because it has the added restriction that the sub-array it chooses must cross the midpoint. Any sub-array crossing the midpoint is itself made of two sub-arrays a[imid] and a[mid+1..j], where i is an index in the left sub-array, and j is an index in the right sub-array. Therefore, we just need to find maximum subarrays of the form a[i..mid] and a[mid+1..j] and then combine them. )

Therefore, to choose MSS as the final answer you need to find the max between these three.

What is the running time of this algorithm? (Note: You can read the complete description of MSS from your textbook: page 70-73)

5) Suppose we have a student who is extraordinarily smart, and decides to solve the Maximum Subsequence Sum problem (MSS) using the below code. What is the running time of this algorithm?

,an) Find the contiguous sub-array with the maximum sum (? ak a. 7, 2,-14,3, 5,-3,4 b. 1,-5, 6,-3, 10,-4, 2, 0, 3 ) of the below array (a,,a,, ksi