# Kadane’s Algorithm

Kadane’s Algorithm is used to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

## Naive Approach

A naive approach to solve this problem would involve checking all possible subarrays and calculating their sums, resulting in a time complexity of `O(n^2)`

.

Kadane’s Algorithm optimizes this by solving the problem in linear time, `O(n)`

, making it highly efficient for large datasets.

## Kadane’s Algorithm

Kadane’s Algorithm works by iterating through the array and keeps track of two variables:

`current_max`

: The maximum sum of the subarray that ends at the current position.`global_max`

: The overall maximum sum found so far across all subarrays.

At each step, the algorithm decides whether to:

`Extend the current subarray`

by adding the current element.`Start a new subarray`

beginning with the current element.

The choice depends on which option yields a higher sum.

## Code

```
def max_subarray(arr):
current_max = arr[0]
overall_max = arr[0]
for i in range(1, len(arr)):
current_max = max(arr[i], current_max + arr[i])
overall_max = max(overall_max, current_max)
return overall_max
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray(arr) # 6
# The maximum contiguous subarray in the given array is [4, -1, 2, 1],
# with a sum of 6.
print("Maximum contiguous subarray sum:", max_sum)
```