ASSIGNMENT 11

#database #productivity #learning #programming

KADANES ALGORITHM

Problem
Find the maximum sum of a contiguous subarray in a given array.

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

Core Insight
At every element, you ask:
--> “Is it better to continue the current subarray or start fresh?”
This single idea drives the entire algorithm.

Intuition
If the running sum becomes worse than the current element
→ Start a new subarray
Otherwise
→ Continue adding

`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`

Step-by-step Dry Run
For:
[-2, 1, -3, 4, -1, 2, 1]
Element
current_sum calculation
current_sum
max_sum
-2
start
-2
-2
1
max(1, -2+1) = 1
1
1
-3
max(-3, 1-3) = -2
-2
1
4
max(4, -2+4) = 4
4
4
-1
max(-1, 4-1) = 3
3
4
2
max(2, 3+2) = 5
5
5
1
max(1, 5+1) = 6
6