Kadanes Algorithm - P2

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

What I Did

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

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

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

How I Solved It

To solve this, I used an efficient approach where I keep updating the sum while moving through the array.

I used two variables:

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

I started both with the first element. Then I looped through the array starting from the second element.

At each step:

• I checked whether it is better to continue the current subarray or start a new one from the current element
• Then I updated the maximum sum if needed

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 only once. At each element, it decides whether to keep adding to the current sum or start fresh.

This way, it avoids checking all possible subarrays and still finds the correct maximum sum efficiently.