**Introduction**

If you are a competitive programmer or someone preparing for campus placements or technical interviews, you have probably come across the following question:

**Given an integer array, find the contiguous subarray (containing at least one number) with the largest sum or in other words the maximum sum contiguous subarray and print its sum.**

If not, does the name Kadane’s Algorithm sound familiar?

It’s alright if you’re hearing this name for the first time. You may be wondering what it is and why we need to solve the problem using Kadane’s algorithm. This article will explain what Kadane’s algorithm is and how to use it. Before delving deeper into the concepts of Kadane’s algorithm, we must first understand what a sub-array is.

**What is a subarray?**

In other words, the problem statement:

An array is a contiguous memory block, as we all know. So, a subarray is a slice of a contiguous array that maintains the order of the elements. It’ll help if you remember that a sub-array may comprise a single element from the given array or the given array as a whole too. The diagram below shows the sub-arrays we can form for the first two elements. To understand this, let us consider an array,

**arr = {1,2,3,4,5}**

For this array, the sub-arrays are:

For element at 0th index | {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5} |
---|---|

For element in 1st index | {2}, {2,3}, {2,3,4}, {2,3,4,5} |

For element in 2nd index | {3}, {3,4}, {3,4,5} |

For element in 3rd index | {4}, {4,5} |

For element in 4th index | {5} |

**What is the Maximum Subarray Problem?**

Now that we have understood what a subarray is, let us understand the Maximum Subarray problem.

In this problem, we have to find the sum which is the maximum of all the sums possible of the contiguous subarrays of the given array. Let us understand this by an example.

Let us take a sample array to be **{****-1,2,-3,4,7,-5****}**.

Now, there are multiple subarrays for this array listed below:

- {-1}
- {-1,2}
- {-1,2,-3}
- {-1,2,-3,4}
- {-1,2,-3,4,7}
- {-1,2,-3,4,7,-5}
- {2}
- {2,-3}
- {2,-3,4}
- {2,-3,4,7}
- {2,-3,4,7,-5}
- {-3}
- {-3,4}
- {-3,4,7}
- {-3,4,7,-5}
- {4}
- {4,7}
- {4,7,-5}
- {7}
- {7,-5}
- {-5}

All these are the possible subarrays for this array.

Now the sums of all these subarrays are:- -1, 1, -2, 2, 9, 4, 2, -1, 3, 10, 5, -3, 1, 8, 3, 4, 11, 6, 7, 2, -5 respectively. We can see that **11** is the maximum sum of all thus this is our result.

**What is Kadane's Algorithm?**

Kadane's Algorithm is an iterative dynamic programming algorithm which means it is a method that is most used to solve finite-dimensional nonlinear constrained global optimal control problems. So, to understand Kadane's Algorithm, we are required to understand Dynamic Programming first. We use Kadane's Algorithm to solve the famous problem - Maximum Subarray Sum. This Algorithm is used for solving the problem in linear time.

**Working of Kadane’s Algorithm**

Some of you may think it’ll be a sum of all elements in an array. But what if there will be negative integer elements in the array, which will decrease the array’s total sum.

Thus, we can see that the sum of all elements in an array isn’t always the case.

A simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array and keep track of the maximum sum contiguous subarray among all positive segments.

- First, we will consider two elements, one which stores the maximum end of the subarray and another which stores the maximum sum so far.

- Let these two variables be
**temp**and**final_ans,**respectively.

- We will initialise
**temp**to 0 and**final_ans**to**INT_MIN**.

- Each time we get a positive sum, we compare it with
**final_ans**and update**final_ans**if it is greater than it.

This logic is written in the form of an algorithm as follows:

- Start

- final_ans = INT_MIN

- temp = 0

- Loop for each element of the array
- if(temp < 0)
- temp = arr[i]

- temp = arr[i]
- else temp = temp + arr[i]

- if(final_ans < temp)
- final_ans = temp

- final_ans = temp

- if(temp < 0)
- return final_ans

Let us understand the working better with the same array we considered before:

Initially, max_so_far = max_ending_here = 0. i is the counter for the loop and it is also initialised with 0.

| Since temp>0 so, temp=temp+arr[i]=0+-1=-1. Now, since -1 is greater than INT_MIN, so final_ans gets updated to -1. |

| Since temp<0 so, temp gets updated to arr[i]=2. Since, temp>final_ans, so final_ans gets updated to 2. |

| Since temp>0 so, temp=temp+arr[i]=2-3=-1. It is smaller than 2 so, final_ans remains as it is. |

| Since temp<0 so, temp gets updated to arr[i]=4. Since, temp>final_ans, so final_ans gets updated to 4. |

| Since temp>0 so, temp=temp+arr[i]=4+7=11. Now, since 11 is greater than 4, so final_ans gets updated to 11. |

| Since temp>0 so, temp=temp+arr[i]=6. Since it is less than 11 so, final_ans remains as it is. |

At the end of all the iterations, the value of final_ans = 11.

Therefore, the maximum contiguous subarray sum is 11.

**Brute Force Approach**

The brute force solution calculates the sum of each subarray and then compares the results to determine the maximum sum of all subarray sums.

The code for the brute force method would be as follows:

**Output**

```
Sum of individual Subarray: -1 1 -2 2 9 4 2 -1 3 10 5 -3 1 8 3 4 11 6 7 2 -5
Maximum Sum Contiguous Subarray = 11
```

This method is straightforward, but we do not use it commonly. Wondering why?

**That is because it has a time complexity of O(N**^{3}**) and O(N) space complexity.**

As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm.

Therefore, we use Kadane’s algorithm because of its advantage considering time and space complexity.

## Implementation of Kadane's Algorithm

Next let us look at the implementation of Kadane's algorithm in C, C++, and Java programs. This will help you understand the algorithm better.

### C Implementation of Kadane's Algorithm

The code given below uses Kadane's Algorithm for finding the maximum subarray sum for the array shown above in C language.

**Output**

`The maximum sum of a contiguous subarray is 11`

Here, we can see that we iterate the elements linearly. We check if the current sum is negative. If it is found negative we initialize it to be the current element's value, else we add the current element to the current sum. We update the final sum if it is greater than the previous one. Finally, we return the maximum sum of a contiguous subarray found.

### Java Implementation of Kadane's Algorithm

The code given below uses Kadane's Algorithm for finding the maximum subarray sum for the array shown above in __Java__ language.

**Output**

`The maximum sum of a contiguous subarray is 11`

Here also the same approach is followed. Because we are programming it in Java language, we make a class named **KadaneAlgorithm. **Inside that class, we have the **Kadane **method to compute the final result.

### C++ Implementation of Kadane's Algorithm

The code given below uses Kadane’s Algorithm to find the maximum subarray sum for the array shown above.

**Output**

`Maximum sum contiguous subarray is 11`

**Time Complexity: O(N)**

**Space Complexity: O(1)**

We saw that the time complexity of Kadane’s algorithm is less than that of the brute force method when solving the same problem.

Hence, Kadane’s algorithm is our preferred method when it comes to finding the maximum contiguous subarray sum.

**Also Read -** __Time Complexity of Sorting Algorithms__

**Advantages of Kadane's Algorithm**

Some of the advantages of Kadane's Algorithm are as follows:

**Simplicity:**Kadane's Algorithm is comparatively easy to implement and understand from other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm**Space Complexity:**This Algorithm has O(1) of space complexity, which means it uses a constant amount of memory despite the size of the input array**Efficiency:**Kadane's Algorithm has an O(n) complexity, which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for big datasets**Dynamic Programming:**This Algorithm is a great example of dynamic programming. Dynamic programming is a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation

**Disadvantages of Kadane's Algorithm**

Some of the disadvantages of kadane's Algorithm are as follows:

**Only finds the sum and not the subarray:**This Algorithm only finds the maximum sum of the subarray and not the actual subarray. If we want to find the subarray that has the maximum sum, we are required to modify the algorithm accordingly.**Not suitable for non-contiguous subarrays:**This Algorithm is specifically designed for contiguous subarrays and is not suitable for non-contiguous subarrays problems.**Does not handle negative value well:**If the input contains only negative value, the algorithm returns the maximum negative number instead of 0.

**Frequently Asked Questions**

**What is Kadane's algorithm?**

Kadane’s algorithm is an iterative dynamic programming algorithm in which we search for a maximum sum contiguous subarray within a one-dimensional array. It operates in O(n) time complexity and O(1) space complexity.

**What is the runtime of Kadane’s algorithm?**

Kadane's algorithm has O(n) run time. where n is the length of the input array. It is a linear-time algorithm that processes each array element only once and is efficient for large inputs.

**What is Kadane's algorithm for maximum product?**

Kadane’s algorithm for maximum product is an iterative dynamic programming algorithm in which we search for a maximum product contiguous subarray within a one-dimensional array. Here also keep the basic understanding of Kadane's algorithm to traverse the elements linearly and keep the maximum of the current product and result product as the result.

**What is Kadane's algorithm for negative numbers?**

For the implementation of Kadane's algorithm, at least one positive number should be present for the final sum. But in cases where all the numbers are negative, we must output the least negative one.

**Conclusion**

This article explains Kadane’s algorithm and how we use it to solve a common question (__maximum subarray sum__) in technical interviews.

Although it appears that the solution should not be as simple as it is, but that’s the beauty of kadane’s algorithm.

There’s no need to collect loads of redundant and additional data about each possible sub-array because we optimise the answer so specifically around collecting only the information we need to know.

**Related Links -**