0 points

Kadane’s Algorithm


dashboard

Wed Dec 25 2019 10:57:06 GMT+0000 (UTC)

Posted by @mishka #c++ #algorithms #interviewquestions #arrays

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

	/* Do not compare for all elements. Compare only 
		when max_ending_here > 0 */
	else if (max_so_far < max_ending_here) 
		max_so_far = max_ending_here; 
} 
return max_so_far; 
} 
content_copy

Given an array, find the subarray with the maximum sum . For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7 for the subarray of {6, -2, -3, 1, 5}

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

>> Browse more code snippets

@czarcurious - Thu Dec 26 2019 18:50:06 GMT+0000 (UTC)

What would someone even need this for?

more_vert