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

Borovinskih · Post by **Borovinskih** » 15 Jan 2002 18:57

по - моему можно так.

int main(int argc, char* argv[])
{
int arr[] = {-3,-1,100,-3,10,-1,-3};
int sum = arr[0];
int maxSum = arr[0];
int maxStart = 0;
int start = 0;
int count = sizeof(arr) / sizeof(arr[0]);

for(int i = 0; i < count; i++)
{
if(sum < 0)
{
sum = arr[i];
start = i;
}
else
{
sum += arr[i];
}

if(maxSum < sum)
{
maxSum = sum;
maxStart = start;
}
}
return 0;
}

Borovinskih · Post by **Borovinskih** » 15 Jan 2002 18:58

блин, умерло форматирование кода и он стал совершенно не читаемым

AK70 · Post by **AK70** » 15 Jan 2002 19:25

<blockquote>quote:<hr>Originally posted by Artem Borovinskih:
блин, умерло форматирование кода и он стал совершенно не читаемым<hr></blockquote>

your code shouldn't work either [img:1ad7c7b18f]images/smiles/icon_smile.gif[/img:1ad7c7b18f] check with my sequence.

tengiz · Post by **tengiz** » 15 Jan 2002 20:09

<blockquote>quote:<hr>Originally posted by AK70:
it should be wrong<hr></blockquote>Well, let me put it this way: it's a classic (and very old) programming puzzle and have been known to have a linear solution (which was already published on Privet). It usually takes 10-20 minutes for smart people to crack it... So, why don't you give it another try? [img:424ba538dd]images/smiles/icon_razz.gif[/img:424ba538dd]

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

<blockquote>quote:<hr>Originally posted by tengiz:
Well, let me put it this way: it's a classic (and very old) programming puzzle and have been known to have a linear solution (which was already published on Privet). It usually takes 10-20 minutes for smart people to crack it... So, why don't you give it another try? [img:c5141dc400]images/smiles/icon_razz.gif[/img:c5141dc400] <hr></blockquote>

well, I don't like bla-bla, I didn't see the right solution yet. if u have ur own, show. or shut up.

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 ]