CPP-Maximum Subarray Sum1

#1

If all the elements of array are negative then it would print 0 as maximum subarray sum which is not the case . so kindly correct it

#2

hey @tushar22.tg.tg, this is the exception of kadane algo that when all numbers are negative, it gives 0. But some modfication can be done in the kadanes such that it will give answer even all numbers are negative.

consider this

int kadane(int arr[], int n)
{
// find maximum element present in given array
int max_num = maximum(arr, n);

// if array contains all negative values, return maximum element
if (max_num < 0)
	return max_num;

// stores maximum sum sub-array found so far
int max_so_far = 0;

// stores maximum sum of sub-array ending at current position
int max_ending_here = 0;

// traverse the given array
for (int i = 0; i < n; i++)
{
	// update maximum sum of sub-array "ending" at index i (by adding
	// current element to maximum sum ending at previous index i-1)
	max_ending_here = max_ending_here + arr[i];

	// if maximum sum is negative, set it to 0 (which represents
	// an empty sub-array)
	max_ending_here = max(max_ending_here, 0);

	// update result if current sub-array sum is found to be greater
	max_so_far = max(max_so_far, max_ending_here);
}

return max_so_far;

}

#3

I am asking for the naive approch O(n^3) and the cumulative sum approach O(n^2)

#4


This is code for maximum subarray sum using cumulative sum approach O(n^2) ,please debug this.
Below link code is giving right answer , i have also written the same-

please help @sanjeetboora

#5

hey @tushar22.tg.tg, in the first code line no 16, make i=1 instead of 0

#6

its already 1 . please send the modified code

#7

hey @tushar22.tg.tg, i=1 in line 22 also.
here is modified code https://ide.codingblocks.com/s/98027

#8

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.