C# Fundamentals, Arrays , MaximalSum of a Sequence - 8 задача!


3

Добър ден!

Прегледах малко коментари относно тази задача - повечето са използвали Kadean's Algorithm. Интересно ми е - има ли и друг начин за постигане на решението? Защото аз се помъчих малко върху нулевия тест с мои си алгоритми и ми излизат , но това само нулевият тест ми излиза! Интересно ми е дали е възможно и по друг начин да се постигне решението , без този алгоритъм? Ако да - да хващам писалката и листчето и да го мисля!




Отговори



0

Здравей! 
Лично аз също използвах Kadane's Algorithm, но въпросът ти ми се стори интересен и намерих описание и за други начини.
Ето тук може да прочетеш малко повече.

Източник1

Източник2

Дано да съм ти помогнала! :)


от ihristova11 (85 точки)


0
Пак ще ми е от полза :) Но дали можем да си измислим наш си алгоритъм или е заложено от закона на математиката да НЯМА друга възможност?

от Edwardcho (30 точки)


0

Здравей, Edwardcho! :)

Ето друг начин:

using System; public class MaximalSum { static void Main() { int n = int.Parse(Console.ReadLine()); int[] arrayNums = new int[n]; for (int i = 0; i < n; i++) { arrayNums[i] = int.Parse(Console.ReadLine()); } int currentSum = 0, maxSum = int.MinValue; for (int i = 0; i < arrayNums.Length; i++) { if (currentSum <= 0) { currentSum = 0; } currentSum += arrayNums[i]; if (currentSum > maxSum) { maxSum = currentSum; } } Console.WriteLine(maxSum); } }


от pepsi_555 (1892 точки)


1
Да, даже 3 пъти по бързо! 

от Edwardcho (30 точки)