Kadene's Algorithm

OVERVIEW
In this task, I worked on finding the maximum sum of a contiguous subarray from a given array. Instead of checking all possible subarrays (which is slow), I used an efficient method called Kadane’s Algorithm.

MY APPROACH
I created a function that takes an array and returns the maximum sum of any subarray

EXAMPLE
Input: arr[-2, 1, -3, 4, -1, 2, 1, -5, 4]
sum : 6
output : arr[4, -1, 2, 1]

LOGIC IMPLEMENTED

1. Traverse the array
2. Add each element to current_sum
3. Update max_sum if current sum is greater
4. If current_sum < 0, reset it to 0

WORKING
The Program keeps adding elements to form a subarray
If the sum becomes negative, it drops that subarray
It always keeps track of the best (maximum) sum seen so far.

This way, we only traverse the array once.

class Solution:
    def maxSubArray(self, arr):
        max_sum = arr[0]
        current_sum = 0

        for num in arr:
            current_sum += num

            if current_sum > max_sum:
                max_sum = current_sum

            if current_sum < 0:
                current_sum = 0

        return max_sum