[C#] Arrays - 8 задача


2
8.Write a program that finds the sequence of maximal sum in given array. Example:

  {2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  ->  {2, -1, 6, 4}

  Can you do it with only one loop (with single scan through the elements of the array)?




Отговори



1

Ето и моето решение на задачата: http://pastebin.com/1UTbQYfs

Използвам съм while и for цилъл  за намиране на редицата с максимална сума. Работи не само с текущия пример. Задачата може да мине само и с while цикъл, но така ми изглежда по-прегледно.


от IvoPN (10 точки)


0
Инициализирането на максималната сума в началото с нула, дали е удачно? А ако числата в масива са само отрицателни? Може би е по-добре в началото да се инициализира с първия елемент на масива.

от Evgenia Hristova (0 точки)

0
Изключителен случай, който не е невъзможен :). Тази част от кода можем да го заменим с int findSum = int.MinValue и подсигуряваме варианта ако масива е само с отрицателни стойностни. Евгения, благодаря за подсказката ! :)

от IvoPN (10 точки)



1

Така и не успях да го измъдря сам как ще стане със един for, но в крайна сметка реализирах първата идея, която ми хрумна и пак върши работа.

http://pastebin.com/GLXqS3wa

btw евала на Kadane за хитрия алгоритъм :D




0

Здравейте колеги,

Някой може ли да си каже мнението за  решението ми  на въпросната задача?

http://pastebin.com/jSN9qTbc

Благодаря предварително!


от Mart1n_Vatev (143 точки)


0
http://pastebin.com/JE6iYQY4
С един цикъл.
Коментирайте ако видите грешка или ако се сетите за подобрение.
Искам да питам дали някой може да ми каже по-модерен начин от:
if (i < endOfSequence - 1) { Console.Write(", "); }
да не ми се появява ", "(запетая и space) след принтиране на последния елемент.
EDIT: добавих малко коментари

от Radvach (357 точки)


0
Може да използваш StringBuilder, като след цикъла намалиш дължината на билдъра с 2. StringBuilder output = new StringBuilder(); for(...) { //for body output.Append(someString); } output.Lenght -= 2;

от emil.venkov12 (1553 точки)

0
Защо казваш на някой да ти зададе размер на редицата, след като в задачата не е казано какъв е той ... а просто да се намери редицата с максимален сбор.




0

Някъде из коментарите не съм сигурен дали в тази тема или друга за тази задача попаднах на това:

http://rerun.me/blog/2012/08/30/maximum-continuous-subarray-problem-kandanes-algorithm/

Л
ично на мен много ми помогна, за да достигна до това решение:

http://pastebin.com/NLYM5Aqj


от kskondov (50 точки)


0

Ето една интересна презентацийка за алгоритъма на Кадейн,която мисля че би ви била много полезна да схванетe нещата по-лесно :)

http://rerun.me/blog/2012/08/30/maximum-continuous-subarray-problem-kandanes-algorithm/


от JulianH (5 точки)


2

Алгоритъмът, който използвам за задачата, е следният: Създавам променливи, в които пазя настоящата и максималната сума, началния и крайния индекс на изследваните редици, както и още две променливи за началния и крайния индекс на редицата с максимална сума. С един for цикъл обхождам масива, като събирам елементите по ред и натрупвам сумата. За всеки следващ елемент се прави следната проверка:

  • ако текущата сума е по-голяма от 0 и е по-голяма от максималната до момента, максималната сума се инициализира с текущата. Запазват се стойностите на началния и крайния индекс на редицата с тази сума.
  • ако текущата сума е по-малка от 0, се инициализира с текущия елемент от масива, а индексът му се задава за начало и край на новата редица

Накрая се инициализира нов масив с елементите от редицата с максимална сума и се отпечатва на конзолата. Решението изглежда така.


от Tanya (202 точки)


0

Здравейте, колеги! Известно време нямах Visual Studio и сега се налага да се боря със задачите от домашното в последния момент. Имам проблем с 8 задача. 

Успявам да изведа елементите, които имат максимална сума, но не винаги смята вярно максималната сума.

Ето го решението:

http://pastebin.com/8w7Fz7v0

Ето и пример, с който не работи: 

n=10 {5, 2, 36, -5, 74, -89, 2, 55, -78, 99}

Пробвах се и с алгоритъм на Кадан, но резултатът е същия.

Може ли малко помощ?


от LERRY (582 точки)


0
На мен ми се струва, че работи... Или си я оправил в откакто си я постнал? :)

от georgiwe (720 точки)

0
Не е оправяна. Казва, че елементите са 5, 2, 36, -5, 74. Но реално сумата = 112, а не на 101.

от LERRY (582 точки)