ASSIGNMENT 10

KADANE'S ALGORITHM

Problem
Given an array of integers (positive + negative), find the maximum sum of a contiguous subarray.

Example:
Id="ex5"
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
👉 Subarray: [4, -1, 2, 1]

Core Idea (This is the MOST important part)
At each step, you decide:
--> “Should I continue the current subarray or start a new one?”
That’s it. *That’s Kadane’s Algorithm.
*

Intuition
If the current sum becomes negative:
It will only reduce future sums
--> So we reset

Step-by-step Logic
Step 1: Initialize
Python id="s1"
max_sum = arr[0]
current_sum = arr[0]

Step 2: Traverse array
Python id="s2"
for i in range(1, len(arr)):

Step 3: Decide (key step)
Python id="s3"
current_sum = max(arr[i], current_sum + arr[i])

👉 Either:
Start new subarray
Continue existing one

Step 4: Update global max
Python id="s4"
max_sum = max(max_sum, current_sum)

*Full Code *
`class Solution:
def maxSubarraySum(self, arr):
max_sum = arr[0]
current_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`

Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
👉 This is optimal

Conclusion
Kadane’s Algorithm:
Finds maximum subarray in one pass
Uses greedy + dynamic programming thinking
Is widely used in real-world problems