Kadane's Algorithm

Objective: Find the contiguous subarray within a given array that has the maximum sum using Kadane's algorithm.

---

Problem Description

Kadane's algorithm is a dynamic programming approach that efficiently solves this problem in O(n) time, where n is the number of elements in the array.

---

Steps to Solve the Problem

1. Initialization:

• Maintain two variables:
  • max_ending_here: Stores the maximum sum of a contiguous subarray ending at the current index.
  • max_so_far: Stores the overall maximum sum of a contiguous subarray found so far.
• Both variables are initialized to the first element of the array.

---

2. Iteration:

• Loop through the array starting from the second element (index 1).
• At each index:
  1. Check Current Element:
     • If the current element (arr[i]) is greater than max_ending_here + arr[i], start a new subarray from the current element:
       max_ending_here = arr[i].
     • Otherwise, extend the current subarray:
       max_ending_here = max_ending_here + arr[i].
  2. Update Overall Maximum:
     • Compare max_ending_here with max_so_far.
     • If max_ending_here is larger, update max_so_far:
       max_so_far = max(max_so_far, max_ending_here).

---

3. Result:

• After iterating through the entire array, max_so_far contains the maximum sum of a contiguous subarray.

---

Example

Input Array:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]

---

Iteration Breakdown:

• Index 0: Element -2
  • max_ending_here = -2
  • max_so_far = -2
• Index 1: Element 1
  • max_ending_here = 1
  • max_so_far = 1
• Index 2: Element -3
  • max_ending_here = -2
  • max_so_far = 1
• Index 3: Element 4
  • max_ending_here = 4
  • max_so_far = 4
• Index 4: Element -1
  • max_ending_here = 3
  • max_so_far = 4
• Index 5: Element 2
  • max_ending_here = 5
  • max_so_far = 5
• Index 6: Element 1
  • max_ending_here = 6
  • max_so_far = 6
• Index 7: Element -5
  • max_ending_here = 1
  • max_so_far = 6
• Index 8: Element 4
  • max_ending_here = 5
  • max_so_far = 6

---

Final Result:

Maximum Sum of a Contiguous Subarray: 6

---

Key Insights

• Kadane's algorithm uses a simple, iterative approach to track the maximum sum, making it efficient and elegant.
• It dynamically adjusts whether to start a new subarray or continue the current one, based on which yields a higher sum.

— Written by Saurabh Patil • B.Tech CSE • Software Developer