Question

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

(a) {0,1,2,3}

(b) {-1,0,1}

(c) {-1,-2,-3,0}

(d) {-4,-3,-2,-1}

The question was posed to me in an international level competition.

My query is from Kadane’s Algorithm in chapter Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct choice is (d) {-4,-3,-2,-1}

The best I can explain: Kadane’s algorithm works if the input array contains at least one non-negative element. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane’s algorithm won’t work.