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




Отговори



4

от ivaylo.kenov (30760 точки)


0
опитай с тази последователност от 5 елемента: 23, 4, -4, -65, 3 (примерно).Така няма да ти изведе последователността.

от Nikimoto (5 точки)

0
Ще го прегледам, благодаря за коментара! :)

от ivaylo.kenov (30760 точки)



12
Kadane's algorithm: http://en.wikipedia.org/wiki/Maximum_subarray_problem
http://pastebin.com/eiUL1UHn



0
Точна така, Kadane's algorithm e най-добрия за целта както и най-бързия - О(n). Аз също съм използвал него за тази задача. http://pastebin.com/Rb0H71a7

от ivivanov (903 точки)

0
Работата е като го тестваш с примерните данни от домашното - не работи :) поне не примерите дадени с Python във Wiki

от dejan (34 точки)


11

Решение:

http://pastebin.com/Vc6Hx12V

Обяснение:

Каква хитрина може да използваме за да не е нужно да използваме 2 цикъла ? Просто проверяваме дали текущата сума е паднала под нула. Ето моята логика:

1. С for цикъла обхождаме всеки елемент по-отделно.

2. След това добавяме стойността на текущия елемент към текущата сума.

3. Използваме StringBuilder за да запазим текущата редичка ( може и с начален и краен индекс, но реших да пробвам по друг начин ). Ако не знаете какво е StringBuilder или метода AppendFormat,не ви е познат вижте тук:

StringBuilder: http://www.dotnetperls.com/stringbuilder

AppendFormat: http://www.dotnetperls.com/appendformat

4. Следващата стъпка е да проверим дали, текущата сума е по-голяма, от най-голямата до сега, ако да присвояваме я като най-голяма и превръщаме редичката от StringBuilder - a в най-добрата редичка до сега.

5. Следващата проверка е дали текущата сума е паднала под нула. Ако това е вярно, нулираме текущата сума и изчистваме съдържанието на StringBuilder - a с метода .Clear()


от Teodor92 (13062 точки)


0
Оправи си първия линк.

от kirov (4821 точки)

0
Какво се случва, ако всички елементи на масива са отрицателни?

от stiliyan.vukadinov (0 точки)



8
Не е най-доброто решение, но е описано подробно в коментарите, ако някой търси обяснено решение: http://pastebin.com/nMtJkFNK

от shristoff (747 точки)


1

Ето и моето решение: source.


от jasssonpet (6814 точки)


0
Здравей, този if е много объркващ. Липсват му фигурните скоби: if (i + j < N) //предотвратява излизане на индекса .....

от nikolaikolarov (2177 точки)

0
Този коментар май е за моето решение. Имаме само един ред, който влиза в if - условието и ми изглежда четливо в случая.

от shristoff (747 точки)


7
Kadane's algorithm:
http://pastebin.com/1BnVm8Kj
инфо в Wiki:
http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm

от anonymous (0 точки)


0
Колежке, не съм сигурен, но може да си погледнаш последния цикъл с който печатиш масива, защото ми се струва, че така няма да работи . Може би трябва да го оставиш да бъде <=end само. Разбрах го защото ми хареса твоето решение, а аз нещо неуспях да го направя и взех идея от решението ти :).

от Svetli (280 точки)

0
Прав си! Благодаря!

от anonymous (0 точки)


1

:) http://pastebin.com/FHLwCvEY

Regards

Iliya


от iliyahristov (0 точки)


2

Ето и моето решение с алгоритъма на Кадан, като съм добавил в началото проверка дали всички елементи на списъка са равни или по малки от нула и ако е така отпечатва най-големия елемент, което се явява и поредицата с най-голяма сума.

http://pastebin.com/uLqnY4FU


от stoyanov (2483 точки)


5
Моето решение е идентично с повечето. Причината да го постна е, че съм се опитал да го направя малко по - разбрано за хората, които не са се занимавали с алгоритми (като мен).
Алгоритъмът на Кадан, елементартно интерпретиран би трябвало да гласи:
Целта е да се намерят началния и крайния индекс на поредицата с най - голяма сума в масив.
Сумираме елементите един по един докато:
1. Намерим елемент, който е по - голям от текущата сума - тук ни е началния индекс.
2. Сумата вече не е максимална - тук ни е крайния индекс.
http://pastebin.com/bqaPf28H

от neofitov (235 точки)


0
пробвах с други числа и не извежда правилната поредица. пример: { 2, 3, 6, -1, 25, -1, 6, 4, -8, 18 } връща целия масив.

от arabella (2576 точки)

0
Еми нормално е да върне целия масив, защото в случая той е редицата с максимална сума :-)

от neofitov (235 точки)


1

На тази задача не мога да схвана нещо... гледайки примера:

 

Example:

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

Как точно събираме елементите на масива - започваме от първия и добавяме всеки следващ? Кога или как разбираме, че трябва да изпуснем, примерно първите 4 елемента?


от todor_pr (1527 точки)


0
Почваме от 1 елемент и пазим най-голямата сума до момента Най - лесно ще го разбереш ,ако си го разпишеш: 1-во: сумата си е 2 =>BestSum=2 2-сумата става 2+3=5 =>BestSum=5 3-сумата става 2+3-6=-1 =>BestSum=5 тук си остава предната, значи не е тая поредица Повечето колеги са го решили с Кадан с 1 цикъл Другият по-лесен начин за който се сетих аз е да изчерпам всички възможни суми с 2 цикъла , ама performance не е много добър за по-големи масиви

от Diagara (277 точки)

0
и моята идея беше такава, за изчерпване на всички суми но как би го направил ти ...ако имаш възможност би ли ми обяснил/

от Miroslava Vitanska (0 точки)