Given an array with negative and positive n element of integers types. Your task to find the contiguous sub-array with maximum sum.
Example
n=4
arr=[4,2,-3,5]
ans=8
now, Out of all ((4),(2),(-3),(5),(4+2),(2+(-3)),((-3)+5),(4+2+(-3)),(2+(-3)+5),(4+2+(-3)+5)) contiguous subarray, The maximum sum of contiguous array is (4+2+-3+5)=8
The basic approach is to find all the Contiguous subarray and then calculate Maximum Sum.
Let us consider a array arr[] of length n and max_ans, temp_sum are the variable for storing answer and temporary answer.
Algorithm: Max_Subarray(arr,n)
Step 1:- Initialize max_ans=0
Step 2:- Repeat step 3 from(i=0 to n-1)
Step 3:- Repeat step 4,5 from(j=i to n-1)
Step 4:- Initialize temp_sum=0
Step 5:- Repeat step 6,7 from(k=i to j)
Step 6:- temp_ans=temp_ans+arr[k]
Step 7:- max_ans=max(temp_ans,max_ans)
max_ans is answer.
This is an optimal solution. The idea behind the algorithm is to initialize two variables max_sum_before=INT_MIN and max_sum_current=0 and start traversing the array and add the element of array in max_sum_current and if the max_sum_current is greater than max_sum_before then update max_sum_before and if max_sum_current is less than 0 then update max_sum_current with 0.
Algorithm: Max_Subarray(arr,n)
Step 1:- Initialize max_sum_current=0 and max_sum_before=INT_MIN
Step 2:- Repeat step 3,4,5 from(i=0 to n-1)
Step 3:- max_sum_current+=arr[i]
Step 4:- if max_sum_current>max_sum_before then max_sum_before=max_sum_current
Step 5:- if max_sum_current==0 then max_sum_current=0
max_sum_before is answer.
Hi