given an array find a subarray with maximum sum

for example if a array has elements [ 1,-3, 2,1,-1] we need to find the maximum sum of the sub array

brute force solution

brute force solution

checking all the possible subarray and picking the one with maximum sum

take two pointers [A,B] take A at zero index position while other B being traversed from 1 to the end of the array in the first step and in the next step take A to the 1 st index position and B being traversed from 2 to the end of the array continue this process and picking the one with maximum sum O(n(square))

kadane’s algorithm

concept

for example x is an element in the array at index N and we know the subarray ending at the ending of previous index is M and the core idea is maximum subarray ending at nth index is either current element[X] or current element combined with previous element [M,X]

code

def Kadane(A):
	max_current = max_global = A[0]
	for i in range(1,length(A)-1):
		max_current = max(A[i] , max_current+A[i])
		if max_current > max_global:
			max_global = max_current
			return max_global

Here how it looks in the iteration table for A=[-2,3,2,-1]