C++ local variable changes value

I have the following c++ function, that is trying to find the maximum subarray sum, within an array of negative and positive integers

int  MaxSubArray::find_max_subarray(void) {
  int maxsofar =0 ;
  int maxendinghere = 0;
  for(int i = 0;i <= arr_size; i++) {
    cout << "maxending here is: " << maxendinghere << endl;
    cout << "maxsofar is: " << maxsofar << endl;
    maxendinghere += array[i];
    maxendinghere = max(0,maxendinghere);
    maxsofar = max(maxendinghere,maxsofar);
  }
  int retvalue = maxsofar;
  cout << "Max so far final is" << maxsofar << endl;
  cout << "Max ending here is " << maxendinghere << endl;
  return retvalue;

}

For an array which contains 10,20,30,-50, 50 I get the following output

maxending here is: 0
maxsofar is: 0
maxending here is: 10
maxsofar is: 10
maxending here is: 30
maxsofar is: 30
maxending here is: 60
maxsofar is: 60
maxending here is: 10
maxsofa开发者_Python百科r is: 60
maxending here is: 60
maxsofar is: 60
Max so far final is135205
Max ending here is 135205
Max sub array is 135205

Can anyone tell me why the variable maxsofar changes value to 135205, outside the for loop. Thanks in advance

Shouldn't it be:

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

?

Note that you modify maxsofar in the last loop iteration after you've printed it, which is why you see a difference - you're probably adding in a garbage value on that last iteration because of your off-by-one loop bounds.

Hope you're enjoying Programming Pearls.

This

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

should be

for(int i = 0; i < arr_size; i++)
                ^^^

You're overstepping the array bound.

for(int i = 0;i <= arr_size; i++) {

Sure that shouldn't be <? Often size means 0 to size-1 is a valid index for that array.

 for(int i = 0;i < arr_size; i++) {

This could be causing you to overwrite your array and write into another stack variable.

Assuming that arr_size is actually the size of the array, your <= operator caused you to run one off the end, addind garbage to the sum.

Because of the loop constraint:

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

You're making one extra step, so you're looking at an index which is outside of the array, and therefor has some random value.

It should be:

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

That's because you have read a junk outside of array bounds:

for(int i = 0;i <= arr_size; i++) { // should be i < arr_size

Your overflowing your array size in your loop. The for loop should read:

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

Note the difference between the <= in your code and the < above. Make the appropriate change and you won't overflow your array. :)

i <= arr_size

Should be

i < arr_size

You print out maxsofar at the top of your loop, so you're not capturing what its value is after the iteration. The values are being changed inside the loop, not outside of it.

This is particularly harmful in your case, since, as others have pointed out, your last iteration goes past the end of the array, adding a nonsense values to your counter.

The idiomatic way to iterate through an array is:

for (int i = 0; i < length; ++i)
{
   // do Stuff
}