To Adak, The problem is that the numbers are not consecutive in values. So 3 can be got from 6 subtracts 2 and 7 is added in.
I got an idea from a friend on how to find max/min values on queues in constant time with insertion and deletion in constant times as well. By applying that idea to here, for each number in the original sequence, maximum 6 operations and minimum 4 operations are needed. So suppose the length of the original sequence is L, solving this problem requires 4L to 6L time, which is O(L) in time complexity. The extract space is very economic as well. The idea is roughly as: Push numbers into a (long enough) queue, at any time find the maximum and minimum numbers in the queue in 1 time. All other operations (push and pop) are finished in constant time. This queue is implemented by two stacks (in one stack we push things in and in another we pop things out). Once the pop is needed for the queue, we pop items from the push stack one by one to the pop stack and then pop items one by one from pop stack. This is the idea of how to make a queue by two stacks. The rest is trivial. I shall find some other ways to show how this is done in details. It is difficult to illustrate well by using word typer as only available here. I will put the link to a pdf file later, showing how I accomplish the whole problem. On Sep 5, 6:13 pm, adak <[EMAIL PROTECTED]> wrote: > Darn it, I meant to post "Sticker shock", but my typo left out the > 't'. . > > Thanks for the clarification, Sticker. > > I believe your algo can be tweaked a bit by simply adjusting your > substring's info when you need to "go back" to the start > of a substring. That is, when you drop the 2 from the substring, and > the new substring begins with 3 in your example, just > subtract 2 from the substring, shorten the L of the substring by 1, > and then add your next number to the substring (making it 3,4,5,6,7), > with > a stop at 8. (from your number 2 to number 3 example). > > >From your description, it sounds like you're rebuilding each substring > > you extend, from scratch, every time you drop a number off the back > end. > > This problem seems very sequentially oriented. I don't see any way to > "divide and conquer" it profitably, either. I like to actually force > myself to solve a bit of it by hand, and then see what "tricks" can be > learned from that exercise. Humans are just so wonderfully lazy and > efficient, sometimes. > > Wish I could be more helpful. > > Anybody have any good tips on this for Sticker? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
