int main()

{

int arr[] = { 1, 3, -5, 7, 2 ,-4, 9, -3};

int length = sizeof(arr) / sizeof(*arr);

int tempSum = 0, maxSum = 0, tempStartIndex = 0, startIndex = 0, endIndex = 0;

for(int i=0; i<length; ++i)

{

tempSum += arr[i];

if(tempSum < 0)

{

tempStartIndex = i+1;

tempSum = 0;

continue;

}

if(tempSum > maxSum)

{

maxSum = tempSum;

startIndex = tempStartIndex;

endIndex = i;

}

}

cout<<"Maximum Sum = "<<maxSum<<" Between indices "<<startIndex<<" "<<

endIndex<<'\n';

return 0;

}

your prog not work for

ReplyDelete3,5 ,8,8,-1,8,6

It is working and the answer is whole array --

ReplyDeleteOutput of Program--

Maximum Sum = 37 Between interval 0 6

Not working for array with all -ve numbers.

ReplyDeleteTwo changes required,

1. Initialize maxsum = a[0]

2. change the order of 'if' inside the for loop.

for(int i=0; i maxSum)

{

maxSum = tempSum;

startIndex = tempStartIndex;

endIndex = i;

}

if(tempSum < 0)

{

tempStartIndex = i+1;

tempSum = 0;

continue;

}

}

Yes, It will not work in that case... I think in the exercise, I have cover that case. Let me know if I did some blunder in that also :)

ReplyDeletehttp://algods-cracker.blogspot.com/2011/10/find-maximum-sum-of-sub-array-within.html