Kadane's Algorithm - CA10

My Thinking and Approach

---

Introduction

In this problem, I was given an array of integers and asked to find the maximum sum of a subarray.

A subarray is a continuous part of the array.

---

Problem Statement

• Given an array of integers arr

• Find the maximum sum of a subarray

• Note:

  • Subarray must contain at least one element
  • Subarray should be continuous

---

My Initial Thought

At first, I considered:

• Generating all possible subarrays
• Calculating their sums
• Finding the maximum

But this approach takes too much time.

---

Key Observation

Instead of checking all subarrays:

• If the current sum becomes negative, it will not help in future
• So, I can reset the sum when it becomes negative

---

Optimized Approach

I decided to use Kadane's Algorithm.

Logic:

• Maintain current sum and maximum sum
• Add elements one by one
• If current sum becomes negative → reset it
• Update maximum sum at each step

---

My Approach (Step-by-Step)

1. Initialize:

• current_sum = arr[0]

• max_sum = arr[0]

  1. Traverse the array from index 1
  2. For each element:

• current_sum = max(arr[i], current_sum + arr[i])

• max_sum = max(max_sum, current_sum)

  1. Return max_sum

---

Code (Python)

Below is the implementation clearly separated inside a code block:

def maxSubArray(arr):
    current_sum = arr[0]
    max_sum = arr[0]

    for i in range(1, len(arr)):
        current_sum = max(arr[i], current_sum + arr[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

---

Example Walkthrough

Input:

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

Steps:

• Start with current_sum = 2, max_sum = 2
• Add 3 → current_sum = 5, max_sum = 5
• Add -8 → current_sum = -3
• Reset → current_sum = 7
• Continue → [7, -1, 2, 3] → sum = 11

Output:

11

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

---

Key Takeaways

• No need to check all subarrays
• Negative sums should be discarded
• Efficient single-pass solution

---

Conclusion

This problem helped me understand how to find the maximum subarray sum efficiently using Kadane's Algorithm.

It is a powerful technique for solving problems related to subarrays.

---