Introduction:
The Kadane's algorithm is a dynamic programming algorithm used to find the maximum sum subarray in an array. It was named after Jay Kadane, who first published the algorithm in 1984. This algorithm efficiently solves the maximum subarray problem, which is a common problem in computer science and has various applications.

Algorithm:
The Kadane's algorithm works by iterating through the array and keeping track of the maximum sum subarray found so far. It uses two variables, maxSoFar and maxEndingHere, to keep track of the maximum sum subarray.

Key Steps:
1. Initialize maxSoFar and maxEndingHere to the first element of the array.
2. Iterate through the array starting from the second element.
3. For each element, update maxEndingHere as the maximum of the current element or the sum of the current element and maxEndingHere.
4. If maxEndingHere is greater than maxSoFar, update maxSoFar to maxEndingHere.
5. Continue this process for all elements in the array.
6. At the end of the iteration, maxSoFar will contain the maximum sum subarray.

Example:
Let's consider an example to illustrate the Kadane's algorithm. Given an array [1, -2, 3, -1, 2], we will apply the algorithm step by step.

- Iteration 1: maxSoFar = 1, maxEndingHere = 1
- Iteration 2: maxSoFar = 1, maxEndingHere = -1
- Iteration 3: maxSoFar = 3, maxEndingHere = 3
- Iteration 4: maxSoFar = 3, maxEndingHere = 2
- Iteration 5: maxSoFar = 3, maxEndingHere = 4

In this example, the maximum sum subarray is [3, -1, 2], and the sum is 4.

Complexity:
The Kadane's algorithm has a time complexity of O(n), where n is the size of the array. This is because it iterates through the array only once. Therefore, it is an efficient algorithm for finding the maximum sum subarray.

Conclusion:
In conclusion, the Kadane's algorithm is used to find the maximum sum subarray in an array. It is a simple and efficient algorithm that solves the maximum subarray problem. By keeping track of the maximum sum subarray found so far, it can efficiently compute the maximum sum subarray in linear time.