Thread: Minimum Positive Subsequence Sum

  1. #1
    Amazingly beautiful user.
    Join Date
    Jul 2005
    If you knew I'd have to kill you

    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?
    Programming Your Mom.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    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. #3
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Minor Problem
    By stewie1986 in forum C Programming
    Replies: 6
    Last Post: 11-30-2007, 08:40 AM
  2. Scheme
    By YankeePride13 in forum A Brief History of
    Replies: 23
    Last Post: 12-18-2005, 04:16 AM
  3. string to int conversion not using atoi()
    By linucksrox in forum C Programming
    Replies: 2
    Last Post: 05-19-2004, 12:17 AM
  4. Help with homework please
    By vleonte in forum C Programming
    Replies: 20
    Last Post: 10-13-2003, 11:16 AM
  5. how to handle integer overflow in C
    By kate1234 in forum C Programming
    Replies: 8
    Last Post: 04-23-2003, 12:20 PM