Algorytmyhard

Jaki problem rozwiązuje algorytm Kadane’a?

Tagi

#kadane#dynamic-programming#array

Odpowiedź

Znajduje maksymalną sumę spójnego (ciągłego) podciągu w O(n), śledząc najlepszą sumę „kończącą się tutaj” i najlepszą globalnie.

function maxSubarraySum(nums: number[]): number {
  let best = nums[0];
  let cur = nums[0];

  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }

  return best;
}

Odpowiedź zaawansowana

Głębiej

Kadane to DP w jednym przebiegu.

Niech:

cur = najlepsza suma podciągu, który musi kończyć się w i
best = najlepsza suma globalnie

Przejście:

cur = max(nums[i], cur + nums[i])
best = max(best, cur)

Dlaczego działa

Jeśli przedłużanie pogarsza wynik, restartujesz w i.

Typowe pułapki

best=0 psuje tablice z samymi ujemnymi; startuj od nums[0].
Mylenie podciągu spójnego z dowolnym podzbiorem.
Zapomnienie, że indeksy da się śledzić pamiętając moment restartu.

Powiązane pytania

Algorytmy

Boyer–Moore majority vote: co rozwiązuje i jaka jest główna idea?

#majority-vote#array#linear-time

Algorytmy

Co liczy algorytm Floyda–Warshalla i jaka jest jego złożoność?

#graphs#shortest-path#floyd-warshall

Algorytmy

DP top-down vs bottom-up — jaka jest różnica?

#dynamic-programming#memoization#tabulation

Algorytmy

Co to jest memoization i kiedy pomaga?

#memoization#dynamic-programming#cache

Algorytmy

Algorytm zachłanny vs programowanie dynamiczne — kluczowa różnica?

#greedy#dynamic-programming#optimization

Algorytmy

Na czym polega technika two pointers?

#two-pointers#array#technique