Saturday, July 31, 2010

Program to find Maximum sum of a subset in an array

I came up with the efficient O(n) solution for this problem. If you have better solution to this problem; Please post your solution as comment. Also remember that, the largest sum could also be among all negative numbers as well, the sum is not necessarily a positive sum.
int MaxSumSubArray(int *a, int len, int *start, int *end) { int max = INT_MIN; int min = 0; int sum = 0; *start = -1; *end = -1; for (int i = 0, j = 0; i < len; i++) { sum += a[i]; if (sum > max) { *start = j; *end = i; max = sum; } if (sum < 0) { j = i + 1; sum = 0; } } return max; } we can call this api as follows: int a[]={-3, -2, -10, -4, -7, -8, -10, -10, -100, -12, -3}; int s1 = 0; int s2 = 0; int sum = MaxSumSubArray(a, sizeof(a)/sizeof(int), &s1, &s2);