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.

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;
}

## All 3 Replies

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.

@Martin B

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

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);

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.