Python - Find the Largest Sum Contiguous Subarray

Python – Find the Largest Sum Contiguous Subarray

This problem, commonly known as the Maximum Subarray Problem, involves finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

Problem Statement

Given an array of integers (which may include both positive and negative numbers), find the contiguous subarray (containing at least one number) that has the largest sum, and return that sum.

Sample Input and Output

Example 1:

</>

Copy

Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum = 6

Example 2:

</>

Copy

Input: arr = [1, 2, 3, 4]
Output: 10
Explanation: The entire array forms the contiguous subarray with the largest sum = 10

Solution Approach

The most efficient solution to this problem is Kadane’s Algorithm, which works as follows:

</>

Copy

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

best_sum: Stores the maximum sum encountered so far (initialize it with the first element of the array).

current_sum: Stores the maximum sum of the subarray ending at the current index (also initialize it with the first element).

current_sum = max(x, current_sum + x) if current_sum is negative, then we have to consider only the element x and the sub array starts with x, otherwise we consider current_sum + x, and the sub array grows by element x.

Python Program

</>

Copy

# Function to find the largest sum contiguous subarray using Kadane's Algorithm
def max_subarray_sum(arr):
    # Initialize max_so_far and current_max with the first element of the array
    max_so_far = current_max = arr[0]
    
    # Iterate through the array starting from the second element
    for num in arr[1:]:
        # Update current_max: decide whether to start a new subarray at the current element or extend the previous subarray
        current_max = max(num, current_max + num)
        # Update max_so_far if the new current_max is greater
        max_so_far = max(max_so_far, current_max)
    
    return max_so_far

# Sample Input 1
arr1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Largest Sum Contiguous Subarray (Example 1):", max_subarray_sum(arr1))

# Sample Input 2
arr2 = [1, 2, 3, 4]
print("Largest Sum Contiguous Subarray (Example 2):", max_subarray_sum(arr2))

Conclusion

Kadane’s Algorithm efficiently solves the Maximum Subarray Problem with a time complexity of O(n) and a space complexity of O(1).

TutorialKart

Python – Find the Largest Sum Contiguous Subarray