Maximum Subarray Sum (Kadane’s Algorithm)

In this task, I worked on finding the maximum sum of a contiguous subarray within a given array. This problem is important because it teaches how to optimize brute-force solutions using dynamic programming concepts. What I Did I created a function maxSubarraySum that takes an array as input and returns the maximum possible sum of any contiguous subarray. Example: Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 How I Solved It A brute-force approach would check all subarrays → O(n²) (too slow). Instead, I used Kadane’s Algorithm, which works in one pass. Step-by-step approach: I initialized: max_sum = first element current_sum = first element Then I looped through the array starting from index 1 For each element: Decide whether to: Start a new subarray (arr[i]) OR extend the existing subarray (current_sum + arr[i]) Update current_sum using: current_sum = max(arr[i], current_sum + arr[i]) Update max_sum if current sum is greater CODE: ''' python class Solution: def maxSubarraySum(self,