Нахождение макс суммы в ряде

Melkor · Post by **Melkor** » 15 Jan 2002 20:21

<blockquote>quote:<hr>Originally posted by AK70:


it should be wrong<hr></blockquote>

В программировании употребление слова "should" обычно означает, что реально имеет место прямо противоположное утверждаемому [img:76d50e12cb]images/smiles/icon_smile.gif[/img:76d50e12cb] . Как и в данном случае, кстати.

clinger · Post by **clinger** » 15 Jan 2002 20:27

<blockquote>quote:<hr>Originally posted by AK70:
check this:
10,-1,100,0,1,-1,10

u see the problem yourself [img:58ed48d4fd]images/smiles/icon_smile.gif[/img:58ed48d4fd]

<hr></blockquote>

Не понял. А в чем проблема? Печатает:

[10, -1, 100, 0, 1, -1, 10]

Или это не верно?

.pl

AK70 · Post by **AK70** » 15 Jan 2002 20:35

<blockquote>quote:<hr>Originally posted by clinger:


Не понял. А в чем проблема? Печатает:

[10, -1, 100, 0, 1, -1, 10]

Или это не верно?

.pl<hr></blockquote>

well, it prints 100,0,1,-1,10 on my PC.

AK70 · Post by **AK70** » 15 Jan 2002 20:39

<blockquote>quote:<hr>Originally posted by Melkor:


В программировании употребление слова "should" обычно означает, что реально имеет место прямо противоположное утверждаемому [img:178d451283]images/smiles/icon_smile.gif[/img:178d451283] . Как и в данном случае, кстати.<hr></blockquote>

intuitively, I feel that there must be a linear solution. but I didn't see it yet. which solution above is linear and correct at the same time? [img:178d451283]images/smiles/icon_smile.gif[/img:178d451283]

Melkor · Post by **Melkor** » 15 Jan 2002 20:53

<blockquote>quote:<hr>Originally posted by AK70:


intuitively, I feel that there must be a linear solution. but I didn't see it yet. which solution above is linear and correct at the same time? [img:a1560515b1]images/smiles/icon_smile.gif[/img:a1560515b1] <hr></blockquote>

Ну, мое, например, а также clinger'a и Artem'a Borovinskih (по сути, это то же самое решение, только шаг разбиения на подмассивы неявно интегрирован в основной цикл; он, по большому счету, нужен только для исследования задачи, а при реализации его таки можно опустить).

AK70 · Post by **AK70** » 15 Jan 2002 22:04

<blockquote>quote:<hr>Originally posted by tengiz:
Uh-oh, you got angry, my friend! [img:a998810a4f]images/smiles/icon_razz.gif[/img:a998810a4f] You shouldn't have, pal - only losers get angry, right? To see the right solution, just read the thread carefully. Or at least read the classics:
Programming Pearls by Jon Louis Bentley, Addison-Wesley Pub Co; ISBN: 0201657880..<hr></blockquote>

ok, I'll check that book. I didn't open it since I first read it.

and, I wasn't angry, btw [img:a998810a4f]images/smiles/icon_smile.gif[/img:a998810a4f]

tengiz · Post by **tengiz** » 16 Jan 2002 09:04

<blockquote>quote:<hr>Originally posted by AK70:
well, I don't like bla-bla, I didn't see the right solution yet. if u have ur own, show. or shut up.<hr></blockquote>Uh-oh, you got angry, my friend! [img:901afb0277]images/smiles/icon_razz.gif[/img:901afb0277] You shouldn't have, pal - only losers get angry, right? To see the right solution, just read the thread carefully. Or at least read the classics:
Programming Pearls by Jon Louis Bentley, Addison-Wesley Pub Co; ISBN: 0201657880..

AK70 · Post by **AK70** » 16 Jan 2002 09:41

ok, guys, there's a O(N) solution [img:02cd68f327]images/smiles/icon_smile.gif[/img:02cd68f327]

I was wrong. btw, it doesn't need the modified array with M elements

[ 15-01-2002: Message edited by: AK70 ]