Kedanes Algorithm

we have a given array of numbers(positive+negative).we have find the maximum sum of the subarray of the array.

as example if we have a=[1,2,-4,5] the result will be "3" because we have the subarray 1,2 which gives the max sum.Other combinations gives minimum result than 3.

logic used:

Kadane’s Algorithm states that,

max_sum[i]=max(a[i],a[i]+max_sum[i-1])

In simple terms, it states that, the maximum sum sub-array ending with A[i], is either the element A[i] itself, or A[i] combined with the maximum sum sub-array ending with A[i – 1], whichever is the greater one.

Code:(python)

a = [int(i) for i in input().split()] final_sum=max_sum=a[0]

#initially the local max and final result is the first element value

for i in range(1,len(a)):

if(a[i]>a[i]+max_sum): max_sum=a[i]

else: max_sum=a[i]+max_sum

if(max_sum>final_sum): final_sum=max_sum print(final_sum)