I understood that the numbers in the sequences, would not be
consecutive. I used consecutive numbers only because
your example had used consecutive numbers.
Glad you found an answer you liked, Sticker. Looking forward to
reading your pdf file.
--~--~-~--~~~---~--~--
whoops, misunderstood the problem - I thought you meant the sum to the
end of the sequence minus the sum to the end. My bad. Please ignore
what I wrote above!
On 6 Sep, 01:21, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]>
wrote:
> I know you've solved the problem, but I'm bored. Would this work? I
I know you've solved the problem, but I'm bored. Would this work? I
was never good at analysing time constraints
Given an array
n_1
n_2
...
n_k
create another array called sums:
n_1
n_1 + n_2
n_1 + n_2 + n_3
n_1 + n_2 + n_3 + ... n_k
Take two indices min and max
min = 0 max = f;
while max < L
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
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 substr
To Adak,
I must clarify the problem. When I mean consecutive numbers, I am not
saying the values are consecutive, but the positions of the numbers.
So in sequence of number {2, 4, 5, 7, 1, 23, 41, 12}, {5, 7, 1} is a
segment of consecutive numbers. But {2, 5, 7} is not because 4 is
missed between
Well, now you've gone and given me Sicker shock! :)
Dilly of a problem, I must say!!
I can't offer you a possible solution, but I'm curious what algorithms
you've tried for this problem, and what was the resulting
performance?
I was thinking, something like:
Scan the numbers, putting all sequ
