DSA: Kadane’s Algorithm

Problem Statement:

Reference — Geeks4Geeks

If Brute Force Approach is followed, we will end up a solution with the complexity of O(n2).

Kadane’s Algorithm reduces the efficiency with complexity as O(n). O(n) explains it should involve linear traversal.

How do we find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum?

It’s simple, let me explain it:

How Kadane’s Algorithm works part 1
How Kadane’s Algorithm works part 2

Points to remember here is

  1. Traverse sequentially/linear way(O(n))
  2. Store maximum sum in the variable
  3. Add till the sum is positive and keep comparing it with maxsum and keep storing the maximum Sum till now
  4. If the sum less than 0 or negative then update it to 0 and start over again

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
komal dongare

komal dongare

Problem Solver, Programmer, Blockchain developer, and a guitarist. New and innovative ideas are always welcomed.