Programming assignment 7.
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.
Hint:
1. 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)
2. For each subarray there are n/2 such subsequence sums. (Find them and save them in 2
different arrays called SL and SR) (e.g. Let’s say that the left subarray is: aL = [ 2, -3, 1, 4, -6]
➔ SL = [2, -1, 0, 4, -2])
3. Using quicksort, sort SL in ascending order and SR in descending order.
4. Define two markers: i and j: Let i be the index marker of SL, and j for SR.
5. Set smin = inf. Now start iterating through SL and SR:
a. If s = SL(i) + SR(j) ≤ 0, then increment i.
b. Else if s < smin, then set smin = s, and increment j,
c. Otherwise, we have s smin, in which case we increment j.
d. Set MPSSmiddle = smin when either the elements of SL or SR have been exhausted.
6. 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).
7. Explain how/why the algorithm for MPSSmiddle works. (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
