Find Largest sum of contiguous Subarray in Python

find Largest sum 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

Algorithm

  • 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.
Python program to find Largest sum of contiguous Subarray

Python Code

Run
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))

Output

Array = [-1, 8, 1, -7, -1, 5, 1, -3]
Sub array which will give maximum sum [8, 1]
Maximum sum = 9

Comments