DSA: Kadane’s Algorithm
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