Может кто-нибудь объяснить этот алгоритм в C ++?
Алгоритм вычисления квадратичной максимальной непрерывной подпоследовательности
int maxSubSum2( const vector<int> & a)
{
int maxSum = 0;
for (int i = 0; i< a.size(); ++i)
{
int thisSum = 0;
for (int j = i; j < a.size(); ++j)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
Мне было интересно, если кто-нибудь может объяснить, как работает алгоритм? Я хорош для циклов, просто плохо для вложенных. «ThisSum» всегда 0 каждый раз, когда выполняется внешний цикл for в строке 8, или он статический?
Большое спасибо! Я очень стараюсь понять алгоритм. Пожалуйста, помогите мне! Я действительно ценю время и усилия.
Решение
Внешний цикл перебирает каждый элемент вектора a, На каждой итерации i будет индекс текущего элемента, он сбрасывает thisSum в 0, а затем выполняет внутренний цикл.
Внутренний цикл перебирает каждый элемент, начиная с i, На каждой итерации j будет индекс его текущего элемента. Затем он вычисляет сумму этих элементов в thisSum,
Внешний цикл заменяет maxSum с thisSum если он выше, чем то, что он уже содержит.
Так что если вектор содержит:
1 7 -10 2 4
последовательные итерации внешнего цикла вычисляют следующие значения thisSum:
1 + 7 + -10 + 2 + 4 = 4
7 + -10 + 2 + 4 = 3
-10 + 2 + 4 = -4
2 + 4 = 6
4 = 4
Первая итерация будет установлена maxSum в 4, После 2-й и 3-й итераций thisSum > maxSum будет ложным, так что это не изменит его. На 4-й итерации 6 > 4так оно и установит maxSum в 6, Последняя итерация не изменит его. Наконец, он вернется 6,
Другие решения
Каждый раз во внешнем цикле for эта сумма сбрасывается в 0 из-за =0 это находится на первой строке внешнего цикла.
Я предлагаю вам изменить вашу функцию, чтобы печатать i, j и thisSum во внутреннем цикле, чтобы вы могли видеть, как они меняются.
Пример а = [1, 2, 3, 4, 5]
j начинается со значения i, поэтому сначала оно начинается с 0, затем 1, затем 2 и так далее. Таким образом, этот второй внутренний цикл уменьшается каждый раз, когда увеличивается внешний цикл.
thisSum сбрасывается в 0 каждый раз, поскольку он НЕ статичен. Если бы это было, это было бы помечено как статическое.
По сути, в этом алгоритме внешний цикл используется для продвижения «начального индекса» вперед, а внутренний цикл используется для фактического сложения всех элементов массива / вектора.
Таким образом, выполнение внутреннего цикла для приведенного выше примера будет выглядеть так:
Execution 1: 1 + 2 + 3 + 4 + 5
Execution 2: 2 + 3 + 4 + 5
Execution 3: 3 + 4 + 5
Execution 4: 4 + 5
Execution 5: 5
Надеюсь, это поможет.
thisSum в вашей строке кода 8 сбрасывается в начальной части цикла я,
но thisSum в вашем цикле J продолжать добавлять массив [] элемент в цикле J.
Обычно я подставляю значение и принимаю значение, чтобы понять, как работает цикл.
Предположим, что вектор a имеет 3 элемента int 10, -20,100
следовательно, a.size () = 3
//maxSum is initialized in the function
int maxSum = 0;
//Start First i loop
int i = 0; i < 3;
int thisSum = 0;
int j = i = 0; j < 3;
thisSum += a[0];
//thisSum = 10
//10 > 0
if (thisSum > maxSum) maxSum = thisSum = 10;
int j = i = 1; j < 3;
thisSum += a[1];
//thisSum = -10
// -10 not > 10
int j = i = 2; j < 3;
thisSum += a[2];
//thisSum = 90
//90 > 10
if (thisSum > maxSum) maxSum = thisSum = 90;
//End First i loop
//Start 2nd i loop
int i = 1; i < 3;
int thisSum = 0;
int j = i = 1; j < 3;
thisSum += a[1];
//thisSum = -20
//-20 not > 90
int j = i = 2; j < 3;
thisSum += a[2];
//thisSum = 80
//80 not > 90
//End 2nd i loop
//Start 3rd i loop
int i = 2; i < 3;
int thisSum = 0;
int j = i = 2; j < 3;
thisSum += a[2];
//thisSum = 100
//100 > 90
if (thisSum > maxSum) maxSum = thisSum = 100;
//End 3rd i loop
//return 100
//return maxSum
Смысл функции заключается в том, что она пытается получить максимальную сумму, шаг за шагом удаляя элемент от наименьшего элемента индекса к наибольшему аргументу индекса.
1-й цикл i: maxSum = 90
2-й цикл i: maxSum = 90 (удалить 10)
3-й цикл i: maxSum = 100 (удалить 10, -20)