In this article we are going to learn about what kadane's algorithm is and will also see how to apply it on 3-dimensional arrays to generate a sub-cube with maximum sum of its elements (3D Kadane's algorithm).

Table of contents:

1. What is kadane algorithm?
2. Algorithm for Kadane’s algorithm
3. 3D Kadane's algorithm for 3D arrays
4. Implementation
5. Time and Space Complexity
6. Applications of 3D Kadane's algorithm

Pre-requisite:

• Kadane's algorithm
• 2D Kadane's algorithm

What is kadane algorithm?

Kadane’s algorithm is an iterative dynamic programming algorithm developed by mathematician Joseph Born Kadane and thusit is named Kadane’s algorithm.
Kadane algorithm is a way to find contiguous max-sum sub-arrays from a given one-dimensional array.
A sub_array is array inside anothr array containing contiguous element.
For e.g.:- If we have an array given by [1,-2,3,4,5,6], then maximum sum contiguous sub- array for this array would be [3,4,5,6] with maximum sum to be 18 which is the summation of 3+4+5+6.

What kadane’s algorithm actually says??

It calculates maximum_sum_sub_array at a particular position using maximum_sum_sub_array at the previous position.

Algorithm for Kadane’s algorithm:-

1 . Declare two variables max_ending_here which stores maximum sum ending at a particular index and max_so_far which stores maximumm sum so far.
2. Iterate over all the elements of array and check whether max_so_far < max_ending_here. If that is the case then update max_so_far.
3. The end max_so_far is the maximum sum in the sub arrays which one can get from the given array.

Example:-

For e.g.:-Take an array [1,-2,3,-1,5].

1. Initialize max_ending_here to be zero, max_so_far to be as less as possible.
2. We begin iterating over the array, at first go over to first element i.e. 1,add it to max_ending_here which now becomes 1, and compare max_so_far with max_ending_here, if max_so_far is greater than max_ending_here, update max_so_far and set it to max_ending_here. Thus, now max_so_far is set to 1.
3. Again, move over to the second element add it to the curr_sum and make it compare to the max_till_now, if max_till_now is less than curr_sum, then update max_till_now to curr_sum else, let it be as it is, also check whetehr curr_sum is less than zero then make it equal to 0. And move over to the next element, do this for all the indices and the final value of max_till_now is the maximum sum of the sub_array which one can get.
4. After the iteration till second element, the curr_sum will be -1 and since, max_till_now is more than curr_sum, thus, its value will not be changed, and curr_sum will be made equal to zero.
5. Similarly, doing the above approaches as mentioned, after the third iteration, curr_sum will be 3, and now since, max_till_now is less than curr_sum, thus, max_till_now will be set to 3.
6. Similarly, after 4th iteration, curr_sum will be equal to 2 and since max_till_now is not less than curr_sum, there will be no change in it.
7. After the 5th iteration, curr_sum will be 7, and since, max_till_now is less than curr_sum, it will be updated to 7.
Thus, in this way, we get maximum sum in contiguous sub_array using kadane's algorithm.

Implementation:-

def kadane(kadane_array,size,left,right,origin_z,inwards):
	max_till_now = -100 # initialize it to be as small as possible.
	curr_sum = 0
	for i in range(0, size):
		curr_sum = curr_sum + kadane_array[i]        
		if (max_till_now < curr_sum):
			max_till_now = curr_sum
		if (curr_sum < 0):
			curr_sum = 0  
	return max_till_now

3D Kadane's algorithm for 3D arrays

Above we have seen how kadane's algorithm can be used to find contiguous sub_arrays. That algorithm an be used in 2-D ,3-D or even n-dimensional arrays to find contiguous sub_arrays(depends how we define contiguos sub_arrays). In case of 2-D we can say we can find contiguous sub-rectangles, while in the case of 3-D we can find contiguous sub-cubes(contiguous sub-rectangles or even just a single element can be a part of it), using kadane's algorithm.
The way by which we tackle the problem of finding the sub-cubes is best understood by taking an example and visualising it to solve our problem.

Pseudocode :-

This is the pseudocode for the traversal of every sub-rectangle for a particular y:-
origin_x,origin_y and origin_z are the lowest values of indices in x dimension, y dimension and z dimension respectively which will most of the time will be equal to zero.
dimension_x, dimension_y and dimension_z are the respective dimensions of 3-d array, for a 2* 2* 2 array, there value being each equal to 2. In our way of kadane's algorithm and element will be denoted by array[value in z_dimension][value in y_dimension][value in x_dimension].

Traversal(3_d_array)
	Initialise an array to store the sums of respective elements for various values of y_axis.
	Initialsie left equal to origin_x(which is 0).
	while(origin_z!=dimension_z):
		Make inwards equal to origin_z(which is 0).
		while(inwards!=dimension_z):
			Make left equal to origin_x(which is 0).
			while(left!=dimension_x):
				Make right equal to left.
				while(right!=dimension_x):
					Make y_axis =0
					while(y_axis!=dimension_y):
                                            Sum the qualifying elements for each value of y_axis.
                                        Append the sum for each value of y_axis into kadane_array.
					kadane(Supply the array containing sum i.e. kadane_array)#Kadane's algorithm is called.
					right+=1
				left+=1
			inwards+=1	
		origin_z+=1	

Understanding pseudocode for traversal with an example:-

Follow the image for the sake of clarity about what is going on while reading at the moment.

Caution:- Open the image in new tab, for better clarity.

3_d_Array is being transferred to function Traversal. Suppose our 3_d_array has dimensions of 2* 2* 2, with its values being :-
[[[-1,2],[0,-3]],[[-2,-1],[1,5]]].
Let origin_z and inwards be corresponding lower and upper limit for values in dimension_z, and let left and right be corresponding lower and upper limit for values in dimension_x. Let kadane_array be the
For the first iteration we enter outermost loop and do whatever is being written in the pseudo-code, after that follow the diagram, and you must get an idea of what is being done in the pseudocode for traversal or how we are traversing the array to make array of sums ready for the kadane's algorithm.

Guide to read image:-First read yellow box, after that move from top left to top right then bottom left to bottom right.

Image dry run.

1. After 1st iteration, in our example our kadane_array=[-1,2] which after getting supplied to kadane's algorithm would make global maximum=2.
2. After 2nd iteration, our kadane_array = [[0][0][1]+[0][0][0] , [0][1][0]+[0][1][1]] = [1,-3]. Thus, no change in global_maximum.
3. After 3rd iteration, our kadane_array = [[0][0][1] , [0][1][1]] = [2,-3]. Thus, again no change in global_maximum.
4. After 4th iteration, our kadane_array = [ [0][0][0] + [1][0][0] , [0][1][0] + [1][1][0]] = [ -3, -1]. Thus, again no change in global_maximum.
5. After 5th iteration, our kadane_array = [[0][0][0] + [1][0][0] + [0][0][1] + [1][0][1], [0][1][0] + [1][1][0] + [0][1][1] + [1][1][1]] = [-2,3], which changes our global maximum to 3.
6. After 6th iteration, our kadane_array = [ [0][0][1] + [1][0][1] , [0][1][1] + [1][1][1] ] = [1,2], thus, no change in global maximum.
7. After 7th iteration, our kadane_array = [ [1][0][0] , [1][1][0] ] = [-2,1], thus, no change in global maximum.
8. After 8th iteration, our kadane_array=[ [1][0][0] + [1][0][1], [1][1][0] + [1][1][1]]=[-3,6], which changes our global maximum to 6.
9. After 9th iteration, our kadane_array=[ [1][0][1], [1][1][1]]=[-1,5], and thus, no change in our global maxima.
10. We come out of every loop and our global maximum value till now becomes our actual global maximum value for the sub-array.

Implementation:-

def Traversal(array,origin_x,origin_z,dimension_x,dimension_y,dimension_z):
	left=origin_x
	while(origin_z!=dimension_z):
		inwards=origin_z
		while(inwards!=dimension_z):
			left=origin_x
			while(left!=dimension_x):
				right=left
				moving_left=left
				while(right!=dimension_x):
					y_axis=0
					sum_in_row=0
					kadane_array=[]
					while(y_axis!=dimension_y):
						moving_inwards=origin_z
						while(moving_inwards!=inwards+1):
							moving_left=left
							
							while(moving_left!=right+1):
								sum_in_row+=array[moving_inwards][y_axis][moving_left]
								moving_left+=1
							moving_inwards+=1
						kadane_array.append(sum_in_row)
						sum_in_row=0
						y_axis+=1
					d=kadane(kadane_array,dimension_y,left,right,origin_z,inwards)#origin_z,inwards) #here, 0 will be the official z1 coordinate. our array will consist of array[0:inwards][y_axis_from_kadane's_algorithm][left:right]
					right+=1
				left+=1
			inwards+=1	
		origin_z+=1	
global Array1
global global_max_#  Stores global maximum out of all arrays supplied to kadane's algorithm
global_max = -10000 # make it as less as possible
Array1=[]
def kadane(kadane_array,size,left,right,origin_z,inwards):
	global global_max
	global Array1
	max_till_now = -10000 # make it as small as possible.
	cur_sum = 0
	y1_index=[]  #used to track the lower limit of y_dimension, where y1 is lower and y2 is upper limit i.e. 0<=y1<=y2<=y_dimension
	for i in range(0, size):
		curr_sum = curr_sum + kadane_array[i] 
		if (max_till_now < curr_sum):
			max_till_now = curr_sum
			y2=i     
		if (curr_sum < 0):
			curr_sum = 0  
            y1_index.append(i+1)#y1_index stores all those indices where curr_sum is equal to zero as lower limit can only be from where sum was taken into consideration
		if(len(y1_index)==0):
            y1=0                
		else:	
			count=0
			for i in range(0,len(y1_index)):            
				if(y1_index[i]>y2 and i!=0):
					y1=y1_index[i-1]# the first index for which y1_index becomes greater than y2, y1's value will be equal to y1_index[i-1] 
					count+=1
					break
				if(y1_index[i]>y2 and i==0):
					y1=0
					count+=1
					break
			if(count==0):
				y1=y1_index[len(y1_index)-1]+1
	if(max_till_now>max_so_fa):
		global_max=max_till_now
		Array1=[global_max,origin_z,inwards,y1,y2,left,right]
	return Array1
Traversal([[[4,8,9],[4,-5,-10],[3,19,-99]],[[4,-11,14],[23,-32,-43],[1,0,-1]],[[-4,-2,23],[-22,56,1],[3,-2,-3]]],0,0,3,3,3)
#outermost bracket is dimension_z, innermost is dimension_x and middle one is dimension_y.


print("Max_sum:", Array1[0])
print("In the 3-d indexing system of Array[Outermost_dimension][Middle_dimension][Innermost_dimension] the range of dimensions of elements forming the maximum sum sub_arrays are:")
print("Innermost_dimesion_varies_from: ",str(Array1[5])+"to"+str(Array1[6]))
print("Middle_dimesion_varies_from: ",str(Array1[3])+"to"+str(Array1[4]))
print("Outermost_dimesion_varies_from: ",str(Array1[1])+"to"+str(Array1[2]))

Time and Space Complexity:-

Time complexity for this problem is O(x_dimension)^2* O(z_dimension)^2* O(y_dimension) O(summing each row’s elemsnts)* O(n){Order of kadane's algorithm}, which for x_dimension=z_dimension=y_dimension becomes
O(n^5)* O(summing each row’s elemsnts)* O(n)

Only difference between this way and the brute force way is the number of ways in which sub-rectangle can be choosen has reduced drastically from O(n^9) to O(n^5), and thus, resultantly we have to sum less.
Space complexity is O(n^3), as that is the amount of space we require to store the input array.

Applications of 3D Kadane's algorithm:-

1. Kadane's algorithm is used for image processing to find broghtest area on images and videos.
   2.It can be used to solve the problmes like "Station Travel in Order" or "Gas Station Problem" which states "There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays of gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1", in this problem we can use a technique known as sliding window used in kadane's algorithm, and with some minor tweakings in which we have to check whether our car can travel from gas station i to (i+1), without getting empty, if it get sempty we simply update the starting position to next gas station and again do the same thing and check whether we can complete a route from any starting point, if we can then we simply print that starting point.
2. Can also be used to solve "Hotels Along The Coast" problem which states "There are N hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.Sroljo has won M Euros on the lottery. Now he wants to buy a sequence of consecutive hotels, such that the sum of the values of these consecutive hotels is as great as possible - but not greater than M." In which problem we are given an array of hotels with their coss, and we need to maximise the number of consecutive hotels choosen, as you would have gotten an idea that kadane's alhorithm can be used, but with the constraint of maximum possible value to be equal to the prize won in the lottery.
   You are to calculate this greatest possible total value.
3. It is used for business analysis, and is used to find the maximum sub array sum for a given n-d array, as we just saw above.