Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
Here's a linear-time algorithm that uses a much different approach than what tye has outlined.. It's probably needlessly dense, but I'm sorry, it came out of my brain in such a form.

If you want to find the best interval within array[i..j], then there are 3 possibilities.

  • The best interval is completely contained within the left half of array[i..j]
  • The best interval is completely contained within the right half of array[i..j].
  • The best interval includes the midpoint of i..j (so it is made up of the best interval in the left half that includes the midpoint, and the best interval in the right half that includes the midpoint).
I'll define a couple of thingies here: OK, so I like to write out dynamic programming algorithms in a logic programming paradigm:
  • best(i,j) is the score of the best interval within array[i..j]
  • lbest(i,j) is the score of the best interval within array[i..j] that includes the left endpoint (i)
  • rbest(i,j) is the score of the best interval within array[i..j] that includes the right endpoint (j)
  • total(i,j) is the sum of the elements in array[i..j].
Here are the rules for the dynamic programming:
lbest(i,i) = rbest(i,i) = best(i,i) = max{ 0, array[i] } best(i,j) = max{ rbest(i,k) + lbest(k+1,j), best(i,k), best(k+1,j) }, where k = int((j+i)/2) lbest(i,j) = max{ total(i,k) + lbest(k+1,j), lbest(i,k) }, where k = int((j+i)/2) rbest(i,j) = max{ rbest(i,k) + total(k+1,j), rbest(k+1,j) }, where k = int((j+i)/2)
We can compute total(i,j) without much overhead by keeping track of an accumulation array (sums of the form array[0..j]). This takes O(n) precomputation for the accumulation sums, and we can compute total(i,j) = sum(array[0..j]) - sum(array[0..i-1]) in constant time.

To compute each lbest(i,j), we split the interval into two intervals of half the size and recurse (with constant computation at this level). So to precompute all the lbest() and rbest() values that we need takes linear time total. Then with all of the lbest() and rbest() precomputed, to compute best(i,j) also just takes two recursive calls for intervals half the size. So the whole algorithm is linear.

OK, so this is probably a lot more machinery than tye suggests, but it gets the job done. I was formulating this before I saw his reply anyway. I wrote some example code for this, but I doubt anyone cares..

There's also the usual pain associated with modifying an algorithm that computes score of the best interval (which this does) to make it return the actual interval itself. ;)

blokhead


In reply to Re: Largest Sum of Consecutive Integers by blokhead
in thread Largest Sum of Consecutive Integers by OverlordQ

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2024-03-28 19:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found