Локальная переменная С++ изменяет значение

У меня есть следующая функция С++, которая пытается найти максимальную сумму подмассива в массиве отрицательных и положительных целых чисел

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;

}

Для массива, содержащего 10,20,30,-50, 50, я получаю следующий вывод

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
maxsofar is: 60
maxending here is: 60
maxsofar is: 60
Max so far final is135205
Max ending here is 135205
Max sub array is 135205

Может ли кто-нибудь сказать мне, почему переменная maxsofar меняет значение на 135205 вне цикла for. заранее спасибо


c++ local
person ppaul74    schedule 02.09.2011    source источник
comment
Просто на скорую руку: вы делаете свои вычисления перед тем, как присвоить значение, возможно, значение изменяется во время последней итерации вашего цикла for. переместите couts ПОСЛЕ ваших назначений и посмотрите на этот вывод.   -  person Chase Henslee    schedule 02.09.2011

Ответы (9)


arrow_upward
4
arrow_downward

Разве не должно быть:

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

?

Обратите внимание, что вы изменяете maxsofar на последней итерации цикла после вывода, поэтому вы видите разницу — вы, вероятно, добавляете ненужное значение на этой последней итерации из-за неправильной настройки. на одну петлю.

Надеюсь, вам нравится Programming Pearls.

person Paul R    schedule 02.09.2011
comment
Да, он делает еще одну итерацию для элемента за пределами массива, что является мусором. - person CMircea; 02.09.2011

arrow_upward
2
arrow_downward

Этот

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

должно быть

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

Вы выходите за границы массива.

person Kerrek SB    schedule 02.09.2011

arrow_upward
1
arrow_downward 

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

Уверены, что это не должно быть <? Часто размер означает, что от 0 до size-1 является допустимым индексом для этого массива.

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

Это может привести к тому, что вы перезапишете свой массив и запишете его в другую переменную стека.

person Doug T.    schedule 02.09.2011

arrow_upward
1
arrow_downward

Предполагая, что arr_size на самом деле является размером массива, ваш оператор <= заставлял вас запускать один с конца, добавляя мусор к сумме.

person Mark B    schedule 02.09.2011

arrow_upward
1
arrow_downward

Из-за ограничения цикла:

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

Вы делаете один дополнительный шаг, поэтому вы смотрите на индекс, который находится за пределами массива и поэтому имеет некоторое случайное значение.

Должен быть:

for(int i = 0;i < arr_size; i++)
person Yochai Timmer    schedule 02.09.2011

arrow_upward
1
arrow_downward

Это потому, что вы прочитали мусор за пределами массива:

for(int i = 0;i <= arr_size; i++) { // should be i < arr_size
person Alexander Poluektov    schedule 02.09.2011

arrow_upward
0
arrow_downward

Ваш размер массива переполняется в вашем цикле. Цикл for должен выглядеть так:

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

Обратите внимание на разницу между <= в вашем коде и < выше. Внесите соответствующие изменения, и вы не будете переполнять свой массив. :)

person mattr-    schedule 02.09.2011

arrow_upward
0
arrow_downward 

i <= arr_size

Должно быть

i < arr_size
person n. 1.8e9-where's-my-share m.    schedule 02.09.2011

arrow_upward
0
arrow_downward

Вы печатаете maxsofar в верхней части цикла, поэтому вы не фиксируете его значение после итерации. Значения изменяются внутри цикла, а не вне его.

Это особенно вредно в вашем случае, поскольку, как указывали другие, ваша последняя итерация проходит за конец массива, добавляя бессмысленные значения к вашему счетчику.

Идиоматический способ перебора массива:

for (int i = 0; i < length; ++i)
{
   // do Stuff
}
person JohnMcG    schedule 02.09.2011
comment
Ой!! Это было действительно глупо с моей стороны. Должен был посмотреть на мой код, прежде чем задавать вопрос. Извините, ребята.. и спасибо за помощь - person ppaul74; 28.12.2011