Kadane's algorithm (max subarray)
Në shqip: Algoritmi i Kadane-s
ShpjegimiSQ
Gjen nënvargun e vazhdueshëm me shumën më të madhe në O(n): ecën nëpër varg dhe vendos në çdo hap nëse vazhdon nënvargun aktual ose fillon një të ri nga ky element.
EnglishEN
Finds the contiguous subarray with the largest sum in O(n): it walks the array and decides at each step whether to extend the current subarray or start a new one from this item.
Si ta mendosh
Si të vendosësh nëse vazhdon me ekipin aktual apo fillon nga e para kur rezultati bie shumë.
Lexoje në anglisht
Like deciding whether to carry on with the current streak or start fresh when the score drops too low.
Shembull kodipython
def maks_nenvarg(v):
aktual = maks = v[0]
for x in v[1:]:
aktual = max(x, aktual + x); maks = max(maks, aktual)
return maks