Kadanes Algorithm - p2

Introduction

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

---

Problem Statement

Given an array of integers, find the maximum sum of a contiguous subarray (containing at least one element).

A subarray is a continuous part of an array.

---

Approach (Kadane’s Algorithm)

We use two variables:

• current_sum → stores current subarray sum
• max_sum → stores maximum sum found so far

Steps:

1. Initialize:

   • current_sum = 0
   • max_sum = -∞

2. Traverse the array:

   • Add element to current_sum
   • Update max_sum
   • If current_sum becomes negative → reset to 0

---

Python Code

python
def kadane(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, 3, -8, 7, -1, 2, 3]
print("Maximum Subarray Sum:", kadane(arr))


## Input
[2, 3, -8, 7, -1, 2, 3]

## output
11

subarray: [7, -1, 2, 3]