Maximum Sum of Contigous Subarray

Given an array with negative and positive n element of integers types. Your task to find the contiguous sub-array with maximum sum.
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

Approach I(Brute-Force)

The basic approach is to find all the Contigous 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.


Approach II(Kadane's Algorithm)

This is optimal solution the idea behind the algorithm is initialize two variable 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 grater then max_sum_before then update max_sum_before and if max_sum_current is less then 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.


Company Tag