Home > Archive > Prolog > October 2004 > Is it NP-complex ?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Is it NP-complex ?
|
|
| Mateusz 2004-10-02, 8:56 pm |
| Hi,
I have to solve one problem, but at first I try to find appropriate
algorithm and
I think that this problem may be NP complex.
There is a some sequence of integers numebrs.
The task is to find the maximum sum but you can take only two consecutive
numbers -
so it's not allowed to take x,x+1,x+2 number where x is the position in the
sequence.
Any ideas ?
Regards
| |
|
| Hint: Nlog(N).
Walter Wilson
Symplicity Business Logic
"Mateusz" <takiegoniema@op.pl> wrote in message
news:cjn0s1$1a7$1@atlantis.news.tpi.pl...
> Hi,
>
> I have to solve one problem, but at first I try to find appropriate
> algorithm and
> I think that this problem may be NP complex.
> There is a some sequence of integers numebrs.
> The task is to find the maximum sum but you can take only two consecutive
> numbers -
> so it's not allowed to take x,x+1,x+2 number where x is the position in
the
> sequence.
> Any ideas ?
>
> Regards
>
>
| |
| Matthias Kretschmer 2004-10-08, 3:57 pm |
| as long as I understand the problem correctly, it is possible to do in
O(N)-time. Even doing it for arbitrary long sequences of sums. Finding
the maximum can be done in time O(N) with a sweep-like algorithm. Doing
it in O(N) is the optimum (as is trivial to see), so we can be very happy :)
--
Matthias
W wrote:[color=darkred]
> Hint: Nlog(N).
>
> Walter Wilson
> Symplicity Business Logic
>
> "Mateusz" <takiegoniema@op.pl> wrote in message
> news:cjn0s1$1a7$1@atlantis.news.tpi.pl...
>
>
> the
>
| |
|
| After rereading the problem statement, I agree (assuming "maximum sum" means
sum of 2 numbers in the list).
Certainly not NP complete.
Walter
"Matthias Kretschmer" <mccratch@gmx.net> wrote in message
news:ck6b4m$t2g$04$1@news.t-online.com...
> as long as I understand the problem correctly, it is possible to do in
> O(N)-time. Even doing it for arbitrary long sequences of sums. Finding
> the maximum can be done in time O(N) with a sweep-like algorithm. Doing
> it in O(N) is the optimum (as is trivial to see), so we can be very happy
:)[color=darkred]
>
> --
> Matthias
>
> W wrote:
consecutive[color=darkred]
|
|
|
|
|