Knowing the subarray with maximum sum using kadane's algorithm

#1

how do we know which subarray has maximum sum. Furthermore it appears that Kadane’s algo cannot be used with array having all negative integers, so please tell all its limitations and how to overcome it.

#2

hey Mayank, You need to maintain beg and end variable if you want to find subarray. Consider this

int maxSoFar = 0; // stores maximum sum subarray found so far
int maxEndingHere = 0; // stores maximum sum of subarray ending at current position

int start = 0, end = 0;  // endpoints of req subarray
int beg = 0;  // stores starting index of a positive sum sequence

for (int i = 0; i < n; i++)
{
	// update maximum sum of subarray "ending" at index i
	maxEndingHere = maxEndingHere + arr[i];

	if (maxEndingHere < 0)
	{
		maxEndingHere = 0;
		beg = i + 1;
	}
	if (maxSoFar < maxEndingHere)
	{
		maxSoFar = maxEndingHere;
		start = beg;
		end = i;
	}
}

for (int i = start; i <= end; i++)
	cout << arr[i] << " ";

Even there are only negative numbers you can modify Kadanes to get your answer. Consider the below code.

int max_so_far = INT_MIN;
int max_ending_here = 0;
int max_element = INT_MIN;

for (int i = 0; i < size; i++)
{
max_ending_here = max(max_ending_here + array[i], 0);
max_so_far = max(max_ending_here, max_so_far);
max_element = max(max_element, array[i]);
}

if (max_so_far == 0)
max_so_far = max_element;

printf("%d\n", max_so_far);