# Thread: Minimum Positive Subsequence Sum

1. ## Minimum Positive Subsequence Sum

I'll preface this by saying this is a homework problem for a data structures class. I'm not looking for you to do the whole problem for me, it's frowned upon, a waste of your time, and a waste of time. On the other hand, I could use a little direction here.

Basically, the maximum subsequence problem is basically "you have an array of integers, find the maximum value you can obtain from a contiguous set of numbers within this array." There's a simple O(n) algorithm for this, because you just loop through the array from the start, and maintain a running sum. If the sum goes below zero, discard it and keep going, because whatever comes after will be larger, without the previous < 0 sum included.

This all makes sense to me, but now our problem is to find the "minimum positive subsequence sum." Playing in my head with the arrays "[-5, 2, 6]" (answer would be 2) and "[-5, 6, 2]" (answer would be 1) I realize I can't just discard for positive values, because I'm not looking for the minimum, I'm looking for the minimum > 0. On the other hand, I can't discard negative values, because they bring it closer to zero, but not every optimal case will include them, because sometimes they prevent a smaller number from being positive.

So, am I missing something, or is an O(N) algorithm impossible in this case? Should I be looking for O(N log N) with something recursive?

2. I have a feeling one-scan won't work -- I can't come up with a scan rule that will handle [2,5,-6,10] (minimum 1). Edit: Now, perhaps one-scan forward and one-scan backward might work....

3. If you scan and save the current minimum? So you read 2. Minimum 2. You read 5. Minimum 2. You read -6. Minimum 1. You read 10. Minimum 1. End. Minimum 1. Seems simple.

EDIT: Of course by minimum I mean a valid >0 minimum.