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 {
increment max until sums[max] - sums[min] >= d
if (sums[max - 1] - sums[min]) < f record max and min
increment min
}
This will give you longest possible sequences that match the
criteria. Since every subsequence would have match the >d criterion,
you just need to list every subsequence where j>f.
How does this look? Kinda new at this, so feedback is appreciated.
On 4 Sep, 03:33, Sticker <[EMAIL PROTECTED]> wrote:
> I have a problem on sequences of numbers:
>
> Given a sequence of integer numbers (could be quite long, let say, 10s
> of thousands of numbers). Let us denote it as
> {n_1,n_2,n_3,n_4,...,n_L}. The length of the sequence is L (meaning
> that it contains L numbers)
>
> >From this sequence I want to find a segment of j consecutive numbers
>
> S={n_i,n_(i+1),n_(i+2),...,n_(i+j)} such that the result of maximum
> number of S minus the minimum number of S is smaller than user defined
> d. The length of the segment j has to be larger than another user
> defined f.
>
> If there are more than one such segment, find them all.
>
> I wonder whether there exists some linear algorithms to handle this
> problem. The solution is better to be quick because it is only a
> subproblem of the complete one and this operation is repeated several
> times.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
