Kadane's Algorithm

#1

How do we get the left and right of the subarray ?

#2

Hey @DrPanda If you are asking about sum of left subarray to maximum sum subarray and sum of right to it as well, we can do that by calculating the prefix sum for the whole array then left subarray sum would be prefix till last element of maximum sum subarray - maximum sum, and right sum would be total sum - prefix till last element of maximum sum subarray.
If this wasnt your question please elaborate the question more.

#3

Sorry for the slight misinformation. I am trying to ask how do we find the position of the left and right elements in the sub array. Please help me to find the elements in the subarray.

#4

okay for this you need to update the left element every time sum becomes less than zero and you initialize it with zero and you need to update the right element every time max_so_far is less than max_so_far.

int maxSubArraySum(int a[], int size) 
{ 
	int max_so_far = INT_MIN, max_ending_here = 0; 
	int left = 0, right = 0, left_temp = 0;
	for (int i = 0; i < size; i++) 
	{ 
		max_ending_here = max_ending_here + a[i]; 
		if (max_so_far < max_ending_here){
			max_so_far = max_ending_here; 
                right = i;
               left = left_temp;
        }

		if (max_ending_here < 0){
			max_ending_here = 0;
          	left_temp = i+1;
        }
	} 
	return max_so_far; 
}
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.