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?
