🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Kadane's Algorithm: all 13 questions

Quiz: Kadane's Algorithm · Question 8 of 13

Kadane's algorithm is an example of which technique?

Kadane's algorithm is an example of which technique?

  1. A.Greedy sorting
  2. B.Binary search
  3. C.Dynamic programming with only the previous state kept
  4. D.Backtracking
Answer & explanation

Correct answer: Dynamic programming with only the previous state kept

best-ending-here[i] = max(a[i], best-ending-here[i − 1] + a[i]) is a DP recurrence that needs only the last value.

Can you get the rest right without peeking?

Take the timed Quiz: Kadane's Algorithm quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →