Question

For which of the following inputs would Kadane’s algorithm produce a WRONG output?

(a) {1,0,-1}

(b) {-1,-2,-3}

(c) {1,2,3}

(d) {0,0,0}

The question was asked in a job interview.

This question is from Kadane’s Algorithm topic in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct option is (b) {-1,-2,-3}

The best I can explain: Kadane’s algorithm doesn’t work for all negative numbers. So, the answer is {-1,-2,-3}.