Finding Largest sum Subarray

[myk45]

Hello.

i was trying to solve this problem:

You’re given an array containing both positive and negative integers and required to find the subarray with the largest sum (O(N)). Write a routine in C for the above.

i was able to find the largest sum. However,i had little trouble finding the subarray.

Can anyone please help?
Thanks.

#include <stdio.h>


int main(void)
{
	int arr[] = {1, 0, -1, -1, 2, 3, 1, -2};
	int sum = 0, max = 0;

	for (int i = 0; i < 8; i++) {
		if (arr[i] < 0) {
			sum = 0;
			continue;			
		} else {
			sum += arr[i];
			
			if (sum > max) {
				max = sum;
			}
		}
	}

	printf("\nAnwser is%d", max);
	getchar();

	return 0;
}

[Martin B]

Actually, you're not quite there with the sum yet.
Try the array {-2, 1, -3, 4, -1, 2, 1, -5, 4}.
The correct sum is 6 (4 + -1 + 2 + 1), but your code gives 4.

[myk45]

@Martin B

Thanks a lot for the reply. i will try to rectify that and get back.

[VIKAS REDDY]

pls check this
int arr[]={-2,1,-3,4,-1,2,1,-5,4};
int sum=0;
int max=0;
for(i=0;i<=8;i++)
{
if(a<=0)
{
sum=sum+a;
if(sum<0)
sum=0;
}
else
{sum=sum+a
}
if(sum>max)
max=sum;
}
printf("%d",max);