Advanced Search

Maximum sub-array sum

/ Published in: C
Save to your folder(s)
Given an array of integers, find the sub-array with maximum sum.

Interesting test cases:

* Empty array.
* One positive element.
* One negative element.
* Two or more elements.
* All negative.
* All positive.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. /*
  2. 	Given an array of integers, find the sub-array with maximum sum.
  3. */
  4. #include<stdio.h>
  5. #include<assert.h>
  6. #define MAX(a,b) ((a) < (b) ? (b) : (a))
  7.  
  8. //Quadratic Algorithm
  9. int maxSubArray1(int array[], int size)
  10. {
  11. 	int maxsofar = 0;
  12. 	for(int i = 0; i < size; i++)
  13. 	{
  14. 		int max = 0;
  15. 		for(int j = i; j < size; j++)
  16. 		{
  17. 			max += array[j];
  18. 			maxsofar = MAX(maxsofar, max);
  19. 		}
  20. 	}
  21. 	return maxsofar;
  22. }
  23.  
  24. //Linear algorithm
  25. int maxSubArray2(int array[], int size)
  26. {
  27. 	int maxsofar = 0;
  28. 	int currentmax = 0;
  29. 	for(int i = 0; i < size; i++)
  30. 	{
  31. 		currentmax = MAX(currentmax + array[i], 0);
  32. 		maxsofar = MAX(maxsofar, currentmax);
  33. 	}
  34. 	return maxsofar;
  35. }
  36.  
  37. int main()
  38. {
  39. 	int array[] = {-1, 2, 4, 28, -30, 50, 60, 80};
  40. 	printf("%d", maxSubArray1(array, 8));
  41. 	return 0;
  42. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.