Kadane’s Algorithm Maximum Subarray Sum

Problem Statement

Given an array of integers, find the contiguous subarray which has the maximum sum and return that sum.

---

Examples

Input
arr = [2, 3, -8, 7, -1, 2, 3]

Output
11

Explanation
The subarray [7, -1, 2, 3] has the maximum sum 11

---

Input
arr = [-2, -4]

Output
-2

---

Approach Using Kadane’s Algorithm

The idea is to iterate through the array and keep track of the maximum sum ending at the current position.

---

Steps

1 Initialize two variables current_sum and max_sum
2 Traverse the array
3 Add current element to current_sum
4 If current_sum is greater than max_sum update max_sum
5 If current_sum becomes negative reset it to zero

---

Code

```python id="kad1"
def maxSubArray