Max Subarray (Kadane)

Easy

Finds the contiguous subarray with the maximum sum in O(n) time.

📊 Complexity

Type	Value
Best	O(n)
Average	O(n)
Worst	O(n)
Space	O(1)

🏷️ Tags

DPArrayGreedy

📖 Introduction

Kadane's Algorithm finds the contiguous subarray with the maximum sum in O(n) time. At each position, simply decide 'continue or start fresh'.

1/29

🎯Maximum Sum of Contiguous Subarray

Find the contiguous subarray with the largest sum! • Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Example: [4, -1, 2, 1] sum = 6 What's the contiguous segment with max sum? Key: Even with negatives, consecutive additions might yield larger sums!

Max Subarray (Kadane)

Easy

Max Subarray (Kadane)

Finds the contiguous subarray with the maximum sum in O(n) time.

📊 Complexity

Type	Value
Best	O(n)
Average	O(n)
Worst	O(n)
Space	O(1)

🏷️ Tags

DPArrayGreedy

📖 Introduction

Kadane's Algorithm finds the contiguous subarray with the maximum sum in O(n) time. At each position, simply decide 'continue or start fresh'.

1/29

🎯Maximum Sum of Contiguous Subarray