[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)?




Отговори



0
Решението: http://pastebin.com/vZYHZrbE
Преди да прочета тази задача си мислех да пререша минала задача за SUM с един цикъл, но лекторите са помислили за всички възможни варианти.

от werew (576 точки)


3

Не съм гледал никакви Кадани, решения на други колеги или съм ползвал гугъл.. /сега мисля да ги погледна след като реших задачата де..човек трябва да се обогатява, това е цялата идея/..тия задачи ми взимат тока, много са ми трудни, незнам как е при вас колеги.../аз решавам една задача между 1 и 2 часа и съм още на 8ма.../

ето моята логика:

1.Правя цикъл който да казва колко последователни числа да се взимат /пример първо да се събират 2 последователни, после три последователни..ит.н./
2.В първия цикъл влагам още един, който да измества броя елементи за сумиране надясно /пример да се сумират 2 последователни елемента, първо с индекси от масива 0 и 1, после 1 и 2, после 2 и 3 и т.н./

3.Във втория правя трети цикъл, който да сумира елементите и да сравнява сумите.

Всичко това е описано и в самото решение:

Sequence Of Maximal Sum In An Array
 


от zhelyazkovn (2949 точки)


0
Подобно е при мен. Задача, два часа! Направо загивам. Днес и вчера цял ден решавам и съм на 8-ма също :( Май ще ме засилят февруари като мръсно коте ;(

от stoyankm (5 точки)

0
i feel your pain :j

от ludmil.d (490 точки)


0
Това е моето решение - http://pastebin.com/2NYDFWb1
Използвам Kadane's Algorithm.

от szaekov (155 точки)


0
Разделяй и владей решение с рекурсия: http://pastebin.com/6rTDauzq
Основната идея е да се раздели проблема на подпроблеми, които се решават лесно и след това се обединяват решенията на подпроблемите, за да се получи решението и на първоначалния проблем.



1
http://pastebin.com/FRFMeqHK
Решението е напълно авторско и съм разгледал някой части случай на задачата, като използвам само един цикъл. Сигурно няма да даде верен отговор при всички комбинации на масиви, но толкова засега.

от andreykata (386 точки)


0
Ето един сравнително лесен подход. Ползвах google за основната идея, като съм вкарвал и частта за изкарване на индексите за изброяване на резултата. Не съм огледал всеоще другите решения (затова и си изгубих половин ден :), и може да се препокривам с някой колега в подхода. Решението: http://pastebin.com/1h4xVryh
Иначе в google има купища неработещи алгоритми по темата, основно този на Кадан (който не работи :)

от dejan (34 точки)


0

http://pastebin.com/mMBghAL1

Решението е аналогично на предходните задачи. Сега е добавено и смятане на сумите на елементите.

Минаваме през всеки един елемент. От начало ако елемента е отрицателен не го взимаме, щом веднъж срещнем положително число, започваме да натрупваме като отчитаме и елемента. Ако срещнем отрицателно пазим временната сума като в последствие проверяваме дали няма да се окаже най-голяма. Ако се окаже по голяма от текущата ще вземем нея.

При този подход, както отбеляза колежката Десислава не дава коректно решение  при само отрицателни числа (защото няма положително число и програмата не заработва реално), затова добавих една булева променлива която да пренасочи решението ако числата са само отрицателни. За целта се добавям още един цикъл за да не се пренатрупва решението..


от stanev.plamen (1143 точки)


0
Ако масива е само с отрицателни числа извежда особен резултат. Също при масив { 6, 3, -6, 10, -2, -1, -6, -4, -8, 8 } извежда резултат 10, а не 13 = ( 6 + 3 + (-6) + 10 ), тъй като като проверява дали (3 + (-6)) < 0, което е така, нулира сумите.. Тук може би текущата сума трябва да се проверява, дали не е отрицателна? При тези проверки за отрицателни числа се изпускат разни работи ;) Поздрави :)


0
Много благодаря за прегледа и намерените пропуски. Да, като вместо да проверявам предходния елемент, проверявам текущата сума работи по-коректно. Това се оправи бързо. Действително програмата при само отрицателни елементи изобщо не зацепва и затова дава 0 - колкото е зададена сумата в началото. Понеделник ще допълня решението че тези задачи с един скан се дават понякога и се иска бърз отговор. Много мерси и успехи :)

от stanev.plamen (1143 точки)


0

Ето и едно интересно решение и от мен, колеги :)

http://pastebin.com/GWJhpnJc

Не е използван споменатият Kadane's algorithm, понеже ми се струва доста сложен и неприложим в случая, тъй като той може да изкара само колко е сумата, но не може да ти изведе точно кои числа от масива дават тая сума...

Приложих си мой алгоритъм, който работи добре :)

Не знам какво ще изведе като резултат, ако се подадат само отрицателни числа... със смесени работи идеално.




1
Ето и моето решение с един цъкъл : http://pastebin.com/feEWxmr4

от KaloyanBobev (330 точки)


0
Имаш само една грешка в това решение - променливата ти first никаде не се променя и това изписва масива от начало. Ако си поиграеш с последните цифри, ще видиш, че сумата се пресмята грешно. Направи така с first: if (maxBegin <= maxEnd) { maxBegin = maxEnd; first = array[index]; last = index; } И всичко е ок, така. Добро решение, иначе.

от wooden_jesus (2128 точки)

0
При array = new int[6]{ 1, -2, 6, 6, -12, 13 }; извежда 6+6 = 12. В този случай, ако отхвърлим поредица от 1 число, вярното трябва да е 6 + 6 - 12 +13 = 13 Проверяваш само дали сумата е останала над 0



1

GitHub

Самото обхождане на масива не става до края а до (в случея) елемента 6 (винаги трябва да има следвващи 3 елемента за да образува сума от 4). Събира всеки 4 елемента и проверява дали сумата е по-голяма от досега намерената максимална.


от dzhenko (3893 точки)