sub array with largest sum

You're given an array containing both positive and negative integers and required to find the sub array with the largest sum in O(N) time or rather in single pass.

Answer:

#include
void FindLargestSubarray( int *a, size_t n)
{
size_t start = a[0];
int sum = a[0];
size_t end = 0;
int intr_sum = 0;
for ( int i = 1; i < n; ++i)
{
intr_sum += a[i];
if ( (sum+intr_sum) >= sum )
{
sum += intr_sum;
end = i;
intr_sum = 0;
}
else if ( a[i] > sum )
{
start = i;
end = i;
sum = a[i];
intr_sum = 0;
}
}
printf("Start %d End %d Sum %d \n", start, end, sum);
}

int main()
{
int a1[] = {10, -20, 30, -60, 50, 80, 0, -60};
int a2[] = {10, 20, 30};
int a3[] = {-99, -5, -1, -100};
FindLargestSubarray(a1, sizeof(a1)/sizeof(a1[0]) );
FindLargestSubarray(a2, sizeof(a2)/sizeof(a2[0]) );
FindLargestSubarray(a3, sizeof(a3)/sizeof(a3[0]) );
return 0;
}

No comments: