Find Largest sum of contiguous Subarray in Python
Largest sum of contiguous sub array
In this article we will see a python program to find Largest sum of contiguous Subarray. User will provide us array which contain some numbers. We are required to find the subarray such that the sum of it is maximum amongst all the possible subarray.
Let us consider an example
- Array= [-1,8,1,-7,-1,5,1,-3]
- Sub array which will maximum product: [8,1,-7,-1,5,1]
- Maximum sum=7
- Step 1: Initialize
- Step 2: Call the function find
Algorithm for function find
- Step 1: Make a variable max_sum and assign -1 value to it. This variable will store the maximum sum.
- Step 2: Make a variable array, which will store the sub array which will give maximum sum.
- Step 3: Iterate on the elements of array using i till length of array. Inside this iteration make another iteration which will iterate from i to length of array. Store sum of the subarray in variable a. If a is greater than max_sum variable’s value then, then assign value of a to max_sum, and then store this subarray in ans variable.
- Step 4: Print the subarray which was giving maximum sum.
- Step 5: Print the maximum of sub array.
def find(arr, l): max_sum = -1 ans =  for i in range(l): for j in range(i, l): a = sum(array[i:j + 1]) if a > max_sum: max_sum = a ans = array[i:j + 1] print("Sub array which will give maximum sum", ans) print("Maximum sum = ", max_sum) array = [-1, 8, 1, -7, -1, 5, 1, -3] print("Array =", array) find(array, len(array))
Array = [-1, 8, 1, -7, -1, 5, 1, -3] Sub array which will give maximum sum [8, 1] Maximum sum = 9