What is the time complexity of kadane's algorithm?

Worst case O(n). Space complexity is O(1).

Kadane's algorithm

medium

Is the run so far helping or hurting? If it has gone negative it can only drag down whatever follows, so discard it. That single comparison is the whole algorithm - and it is dynamic programming in disguise.

Worst O(n)Space O(1)

Loading the kadane's algorithm engine…

Where to go next

Fixed sliding window

easy

Two operations replace k additions.

House robber

easy

Two choices per house, and the table collapses to two variables.

Prefix sums

easy

Precompute once, answer every range query in O(1).