Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0
Notifications Mark All Read
- Login
- Get Prime
0
Find Largest sum of contiguous Subarray in Python
Related Banners
Prepinsta Prime
Get Prepinsta Prime
Get all 200+ courses offered by Prepinsta
Check out our instagram
Instagram
Whatsapp
Telegram
LinkedinGet Hiring Updates
Amazon,Google,Delottie & 30+companies are hiring ! Get hiring Updates right in your inbox from PrepInsta
PrepInsta Prime
Get over 200+ course One Subscription
PrepInsta Prime
Get over 200+ course One Subscription
Get PrepInsta Prime Subscription
Companies
TCS, Cognizant, Delloite, Infosys, Wipro, CoCubes, KPMG, Amazone, ZS Associates, Accenture, Congnizant & other 50+ companies
Programming
Data Structures, Top 500 Codes, C, C++, Java Python & other 10+ subjects
Skills
Full Stack Web Development, Data Science, Machine Learning, AWS Cloud, & other 10+ skills and 20+ projects
Companies
TCS, Cognizant, Delloite, Infosys, Wipro, CoCubes, KPMG, Amazone, ZS Associates, Accenture, Congnizant & other 50+ companies
Programming
TCS, Cognizant, Delloite, Infosys, Wipro, CoCubes, KPMG, Amazone, ZS Associates, Accenture, Congnizant & other 50+ companies
Skills
TCS, Cognizant, Delloite, Infosys, Wipro, CoCubes, KPMG, Amazone, ZS Associates, Accenture, Congnizant & other 50+ companies
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 Code
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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Login/Signup to comment