Kadanes Algorithm

In this task, I worked on finding the maximum sum of a subarray within a given array. A subarray means a continuous part of the array, and the goal is to find the part that gives the highest sum.

What I Did

I created a function called max_subarray_sum that takes an array of numbers and returns the maximum possible sum from any continuous subarray.

For example:
Input: [2, 3, -8, 7, -1, 2, 3]
Output: 11

This comes from the subarray [7, -1, 2, 3].

How I Solved It

To solve this, I used a method where I keep track of two values:

• current_sum → the sum of the current subarray
• max_sum → the maximum sum found so far

I started both with the first element of the array. Then I looped through the rest of the elements.

At each step:

• I decided whether to continue the current subarray or start a new one
• Then I updated the maximum sum if the current sum is greater

Code

def max_subarray_sum(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
print(max_subarray_sum([2, 3, -8, 7, -1, 2, 3]))
print(max_subarray_sum([-2, -4]))
print(max_subarray_sum([5, 4, 1, 7, 8]))

How It Works

The function goes through the array once and keeps updating the running sum. If adding the current element makes the sum worse, it starts fresh from that element.

This way, it always keeps track of the best possible subarray sum found so far without checking all combinations.