Kadanes Algorithm

Introduction

Kadane’s Algorithm is an efficient way to find the maximum sum of a contiguous subarray. It is widely used in array and dynamic programming problems.

---

Problem Statement

Given an array of integers (both positive and negative), find the contiguous subarray with the maximum sum and return that sum.

---

Approach (Kadane’s Algorithm)

We use a dynamic approach:

1. Initialize two variables:

   • current_sum = 0
   • max_sum = very small number

2. Traverse the array:

   • Add current element to current_sum
   • If current_sum becomes greater than max_sum → update max_sum
   • If current_sum becomes negative → reset it to 0

---

Python Code

python
def max_subarray_sum(arr):
    current_sum = 0
    max_sum = float('-inf')

    for num in arr:
        current_sum += num
        max_sum = max(max_sum, current_sum)

        if current_sum < 0:
            current_sum = 0

    return max_sum

# Example
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", max_subarray_sum(arr))


## Input
  [-2, 1, -3, 4, -1, 2, 1, -5, 4]

## Output
   6