← 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?
- A.Greedy sorting
- B.Binary search
- C.Dynamic programming with only the previous state kept
- 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 →