Может ли кто-нибудь объяснить этот алгоритм на C++?

Question

Квадратное Максимальная сумма алгоритм смежный подпоследовательности

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 каждый раз, когда выполняется цикл внешнего цикла в строке 8 или он статичен?

спасибо! Я очень стараюсь понять алгоритм. Пожалуйста, помогите мне! Я очень ценю время и силы.

Answer 1

Каждый раз, когда внешние петли цикла, эта сумма сбрасывается на 0 из-за =0, которая находится в первой строке внешнего контура.

Предлагаю вам изменить свою функцию для печати i, j и thisSum во внутреннем цикле, чтобы вы могли видеть, как они меняются.

Answer 2

Внешняя петля итерации по каждому элементу вектора 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.

Answer 3

Пример а = [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 

Надежда, что помогает.

Answer 4

thisSum на свой код линии 8 сбрасывается в начальной части цикла я,

но thisSum в цикле J является держать добавить массив а [] элемент в цикле J.

---

Обычно я подставляю значение и принимаю значение, чтобы понять, как работает цикл.

Пусть Предположим, вектор а имеет 3 ИНТ элементы 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 

Понятие функции является его пытаются получить максимальную сумму за шагом шаг за шагом удалите элемент из наименьшего элемента индекса в самый большой аргумент индекса.

первый цикл я: maxSum = 90

второй цикл я: maxSum = 90 (удалить 10)

3-й цикл я: maxSum = 100 (удаление 10, -20)