Lecture 115:- Max Sub Array Sum

The maximum subarray sum problem involves finding the contiguous subarray within a given array of integers that has the largest sum. This is a classic problem in computer science and can be solved using various algorithms and techniques.

One well-known algorithm for solving the maximum subarray sum problem is the "Kadane's Algorithm." Here's how Kadane's Algorithm works:

pythonCopy code

def max_subarray_sum(arr): max_ending_here = max_so_far = arr[0] for num in arr[1:]: max_ending_here = max(num, max_ending_here + num) max_so_far = max(max_so_far, max_ending_here) return max_so_far # Example usage arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] result = max_subarray_sum(arr) print("Maximum subarray sum:", result)

In this example, the function max_subarray_sum uses Kadane's Algorithm to find the maximum subarray sum in the given array. The algorithm maintains two variables: max_ending_here represents the maximum sum ending at the current index, and max_so_far represents the maximum sum seen so far.

The algorithm iterates through the array and at each step, it updates max_ending_here by either starting a new subarray or extending the current subarray. It also updates max_so_far to keep track of the overall maximum subarray sum encountered.

The time complexity of Kadane's Algorithm is O(n), where n is the length of the input array, making it an efficient solution for this problem.

Keep in mind that if all the elements in the array are negative, the algorithm will return 0 (indicating an empty subarray). If you want the algorithm to consider cases where the entire array is negative, you can modify it accordingly.