Find the contiguous subarray with the largest sum Python Program

 Maximum Subarray Sum: Find the contiguous subarray with the largest sum Python Program?

To find the contiguous subarray with the largest sum, you can use Kadane's Algorithm. This algorithm is efficient and works in linear time, making it well-suited for this problem. It keeps track of the maximum sum of the subarray ending at the current position and updates the global maximum sum accordingly.

Kadane's Algorithm

1. Initialize Variables:

   • current_sum to store the maximum sum of the subarray ending at the current position.
   • max_sum to store the maximum sum found so far.

2. Iterate Through the Array:

   • For each element, update current_sum to be the maximum of the current element itself or the current element plus current_sum from the previous element.
   • Update max_sum to be the maximum of max_sum or current_sum.

3. Return the Result:

   • After iterating through the array, max_sum will contain the maximum sum of any contiguous subarray.

Python Implementation

Here is a Python implementation of Kadane's Algorithm:

def max_subarray_sum(nums):

    if not nums:

        return 0

    

    current_sum = max_sum = nums[0]

    

    for num in nums[1:]:

        # Update current_sum to be the maximum of the current element or

        # the current element plus the current_sum of the previous subarray

        current_sum = max(num, current_sum + num)

        

        # Update max_sum to be the maximum of itself and current_sum

        max_sum = max(max_sum, current_sum)

    

    return max_sum

# Example usage:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

print(max_subarray_sum(nums))  # Output: 6 (subarray: [4, -1, 2, 1])

Explanation

1. Initialization:

   • current_sum and max_sum are both initialized to the first element of the array. This is because the smallest possible subarray is the array with just one element.

2. Iteration:

   • For each subsequent element, decide whether to include it in the current subarray (current_sum + num) or start a new subarray with the current element (num).
   • Update current_sum with the maximum of these two options.
   • Update max_sum to ensure it holds the largest value found so far.

3. Edge Cases:

   • The code handles cases with only one element and negative numbers by initializing current_sum and max_sum with the first element.

Complexity

• Time Complexity: $O(n)$, where $n$ is the number of elements in the array. Each element is processed exactly once.
• Space Complexity: $O(1)$. The algorithm uses a constant amount of space regardless of the input size.

Kadane's Algorithm is a powerful technique for solving the maximum subarray sum problem efficiently.