Maximum Subarray: Write a program that finds the contiguous subarray or maximum subarray in python within a one-dimensional array of numbers that has the largest sum.
- Program to Create Snake Game in Python
- Write a Program to Create Hangman Game in Python
- Program to Create Tic Tac Toe Game in Python
- Program to Create BlackJack Game in Python
- Program to Solve Traveling Salesman Problem in Python
Introduction to Maximum subarray in Python:
Finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum is a classic problem in computer science. This problem is also known as the Maximum Subarray Problem. It is often used as an interview question to test a candidate ability to write efficient algorithms. In this article we will walk through the steps to solve this problem using Python.
Problem Statement:
Given an array of integers, we need to find the contiguous subarray that has the largest sum.
For example,
Let’s say we have an array of numbers: [1, -2, 3, 10, -4, 7, 2, -5].
The contiguous subarray with the largest sum is [3, 10, -4, 7, 2], which has a sum of 18.
Approach to find maximum subarray in python:
We can solve this problem by iterating through array and keeping track of maximum sum we have seen so far. We will start with initial maximum sum of the first element in the array and we will update it as we iterate through the array. We will also keep track of the sum of the current subarray which we will reset to 0 if it becomes negative.
Algorithm to find maximum subarray in python:
- Initialize two variables
max_sumandcurr_sumto the first element in the array. - Iterate through the array starting with the second element.
- At each iteration add the current element to
curr_sum. - If
curr_sumis greater thanmax_sumupdatemax_sumto be equal tocurr_sum. - If
curr_sumbecomes negative reset it to 0. - Return
max_sum.
Code to find maximum subarray in python:
Here is the Python code that implements the maximum subarray algorithm:
def find_largest_subarray(arr):
max_sum = curr_sum = arr[0]
for num in arr[1:]:
curr_sum += num
if curr_sum > max_sum:
max_sum = curr_sum
if curr_sum < 0:
curr_sum = 0
return max_sum
Testing:
Let’s test the find_largest_subarray() function on the example array we used in the problem statement:
arr = [1, -2, 3, 10, -4, 7, 2, -5]
largest_sum = find_largest_subarray(arr)
print(f"The largest sum of a contiguous subarray is: {largest_sum}")
This should output:
The largest sum of a contiguous subarray is: 18
Time Complexity to Find Maximum Subarray in Python
Time complexity of algorithm to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum is O(n) where n is the number of elements in the array. This is because algorithm only iterates through the array once and at each iteration it perform a constant number of operations. Therefore the algorithm is very efficient and can handle large arrays with a minimal amount of computational overhead.
Conclusion:
In this article we have walked through the steps to solve the Maximum Subarray Problem using Python. We have explained the problem statement the approach and algorithm used to solve the problem. We have also provided Python code to implement the algorithm and we have tested the code on an example array. This is a classic problem in computer science and it is often used as an interview question to test a candidate’s ability to write efficient algorithms.