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 divide and conquer algorithm for MSS, but now it is not so easy to compute

MPSS_{middle}, **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 S_{L}and S_{R}) (**g.**Let’s say that the left subarray is: a_{L}= [ 2, -3, 1, 4, -6] ➔ S_{L}= [2, -1, 0, 4, -2]) - Using quicksort, sort S
_{L}in*ascending*order and S_{R}in*descending* - Define two markers: i and j: Let i be the index marker of S
_{L}, and j for S_{R}. - Set s
_{min}=*inf*. Now start iterating through S_{L}and S_{R}:- If s = S
_{L}(i) + S_{R}(j) ≤ 0, then increment i. - Else if s < s
_{min}, then set s_{min}= s, and increment j, - Otherwise, we have s > s
_{min}, in which case we increment j. - Set MPSS
_{middle}= s_{min}when either the elements of S_{L}or S_{R}have been exhausted.

- If s = S
__Calculate__the time complexity of your algorithm for finding MPSS on paper and show your answer to me. Running time should satisfies*T(n) = Θ(nlog*^{2}n).- Explain how/why the algorithm for MPSS
_{middle}(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

## Reviews

There are no reviews yet.