Programming assignment 6.
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:
➢ Use the same idea of 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)
To find MPSSmiddle:
1. 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])
2. Using quicksort, sort SL in ascending order and SR in descending order.
3. Define two markers: i and j: Let i be the index marker of SL, and j for SR.
4. 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 the elements of SL and SR have been exhausted.
5. 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).
6. Explain how/why the algorithm for MPSSmiddle works. (You may write your answer on
paper)
Ask the user for the size of the array (n) and generate n random numbers between -20 to 20.
Example:
Input: A = [2, -3, 1, 4, -6, 10, -12, 5.2, 3.6, -8],
Output: MPSS = 0.8
