# DSA: Kadane’s Algorithm

Problem Statement:

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:

Points to remember here is

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