Write a recursive function to calculate the minimum positive subsequence sum (MPSS). In other words, of all subsequences whose sum adds to a positive number, you want to determine the minimum of such sums.
- Use the same divide and conquer algorithm for MSS, but now it is not so easy to compute
MPSSmiddle, Explain why? (You could make a counter example on a piece of paper)
- For each subarray there are n/2 such subsequence sums. (Find them and save them in 2 different arrays called SL and SR) (g. Let’s say that the left subarray is: aL = [ 2, -3, 1, 4, -6] ➔ SL = [2, -1, 0, 4, -2])
- Using quicksort, sort SL in ascending order and SR in descending
- Define two markers: i and j: Let i be the index marker of SL, and j for SR.
- Set smin = inf. Now start iterating through SL and SR:
- If s = SL(i) + SR(j) ≤ 0, then increment i.
- Else if s < smin, then set smin = s, and increment j,
- Otherwise, we have s > smin, in which case we increment j.
- Set MPSSmiddle = smin when either the elements of SL or SR have been exhausted.
- Calculate the time complexity of your algorithm for finding MPSS on paper and show your answer to me. Running time should satisfies T(n) = Θ(nlog2 n).
- Explain how/why the algorithm for MPSSmiddle (You may write your answer on paper)
Example: Ask the user to give you the size of the array (n) and generate n random numbers between -20 to 20.
A = [2, -3, 1, 4, -6, 10, -12, 5.2, 3.6, -8], Output:
MPSS = 0.8