Array is almost, in some way, in every application of programming and computer science in general. With array being so important in practical application any procedure on array becomes significant.

In this post we will look at the problem of finding **maximum sub-array sum** which can be done efficiently by using **Kadane's Algorithm**.

** Note** : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.

## Problem Statement

Given an array of elements A, find the maximum sub-array sum.

**Note** : Sub-array is a collection or block of contiguous items in an array.

Example : For array A[]={1, 2, 3, 4}, {1, 2} is a sub-array whereas {1, 3} is not.

## Naive Approach

Loosely speaking, we can traverse each and every subset that can be generated and calculate the sum for each and every possible subset.

*Pseudo Code :*

```
maxsum=0
for i=0 upto A.length
sum=0
for j=i+1 upto A.length
sum=sum+A[j]
if(sum>maxsum)
maxsum=sum
```

**Time Complexity **:** O(|A| ^{2})**

**Space Complexity **:** O(|A|)**

## Kadane's Algorithm

The approach of Kadane's Algorithm is simple. We keep two flags, namely **maxSum** and **currSum** which store the global maximum and the local maximum respectively.

At each iteration we update the **currSum** as the maximum of **currSum+currElement** and **currElement**.

- If currSum + currElement is bigger then, we are adding to a sub-array started at a position before the currElement's position.
- If currElement is bigger then, we are considering the sub-array that is starting at the currElement's position.

At each iteration, we also update the maxSum by checking if the local maximum is the global maximum i.e. we update **maxSum** to be the maximum of **maxSum** and **currSum**.

Example : Let us consider an array A[]={12, 23, -38, 1, 2}.

- We initialise
**maxSum**,**currSum**with the value at**A[0]**.

- At index 1, we update the value of
**currSum=max(12, 12+23)=35**and**maxSum=max(12, 35)**.

- At index 2, we update the value of
**currSum=max((-38), 35+(-38))=-3**whereas the value of**maxSum**remains unchanged.

- At index 3, we update the value of
**currSum=max(1, 1+(-3))=1**and the value of**maxSum**remains unchanged.

- At index 4, we update the value of
**currSum=max(2, 2+1)=3**and the value of**maxSum**remains unchanged.

Hence, the maximum sub-array sum for this array A is **maxSum=35**.

*Pseudo Code :*

```
maxSum=currSum=A[0]
for i=1 upto A.length
currSum=max(A[i], currSum+A[i])
maxSum=max(maxSum, currSum)
```

**Time Complexity : O(|A|)**

**Space Complexity : O(|A|)**

Kadane's Algorithm is one simple algorithm that in a very few lines of code finds the maximum sub-array sum of an array. This algorithm can be applied for **business analysis** to study sales, profits and losses so as to make judicial business decisions.