Posted By

jaircazarin on 10/01/08


Tagged

Algorithms Microsoft-Interview


Versions (?)

Who likes this?

2 people have marked this snippet as a favorite

jaircazarin
sergeizen


Maximum sub-array sum


 / Published in: C
 

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.
  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  

You need to login to post a comment.