有人能在c++中解释这个算法吗?

Quadratic Maximum contiguous subsequence sum algorithm

二次最大连续子序列和算法

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;
}

I was wondering if anyone can explain how the algorithm works? I am good with for loops, I'm just bad at nested ones. Is "thisSum" always 0 every time the outer for loop on line 8 runs or is it static?

我想知道是否有人能解释这个算法是如何工作的?我很擅长循环，只是不擅长嵌套循环。第8行上的外for循环每次都是0，还是静态的?

Thank you very much! I am trying really hard to understand the algorithm. Please help me! I really appreciate the time and effort.

非常感谢!我正在努力理解这个算法。请帮助我!我真的很感谢你花的时间和精力。

4 个解决方案

#1

The outer loop iterates over every element of the vector a. On each iteration, i will be the index of the current element, it resets thisSum to 0, and it then executes the inner loop.

外循环遍历向量a的每个元素。在每次迭代中，i将是当前元素的索引，它将thisSum重置为0，然后执行内部循环。

The inner loop iterates over every element starting from i. On each iteration, j will be the index of its current element. It then calculates the sum of these elements in thisSum.

内循环从i开始遍历每个元素，在每次迭代中，j都是当前元素的索引。然后它计算出这些元素的和。

The outer loop replaces maxSum with thisSum if it's higher than what it already contains.

如果maxSum的值高于它已经包含的值，则外部循环将其替换为th问题m。

So if the vector contains:

如果这个向量包含

1 7 -10 2 4

the successive iterations of the outer loop will calculate the following values of thisSum:

外环的连续迭代将计算出th问题m的如下值:

1 + 7 + -10 + 2 + 4 = 4
7 + -10 + 2 + 4 = 3
-10 + 2 + 4 = -4
2 + 4 = 6
4 = 4

The first iteration it will set maxSum to 4. After the 2nd and 3rd iterations, thisSum > maxSum will be false, so it won't change it. On the 4th iteration, 6 > 4, so it will set maxSum to 6. The last iteration won't change it. Finally, it will return 6.

第一次迭代将maxSum设置为4。在第2和第3次迭代之后，thisSum > maxSum将是假的，因此不会更改它。在第4次迭代中，6 > 4，因此它将maxSum设置为6。最后一次迭代不会改变它。最后，它将返回6。

#2

Every time the outer for loop loops, this sum is reset to 0 because of the =0 that is on the first line of the outer loop.

每次外部for循环循环，这个和都被重置为0，因为在外部循环的第一行上=0。

I suggest you modify your function to print i, j, and thisSum in the inner loop so that you can see how they are changing.

我建议您修改您的函数，使其在内部循环中打印I、j和thisSum，以便您可以看到它们是如何变化的。

#3

Example a = [1, 2, 3, 4, 5]

示例a = [1, 2, 3, 4, 5]

j starts at the value of i, so it will first start at 0, then 1, then 2 and so on. Thus this second, inner loop is smaller each time the outer loop increments.

j从i的值开始，所以它首先从0开始，然后1，然后2，以此类推。因此，这一秒内循环在每次外循环增加时都更小。

thisSum is reset to 0 each time as it is NOT static. If it was, it would be labeled static.

每次当它不是静态的时候，它被重置为0。如果是，它将被标记为静态。

Basically, in this algorithm the outer loop is used to push the 'starting index' forward, with the inner loop used to actually add all the elements of the array / vector together.

基本上，在这个算法中，外部循环用于将“开始索引”向前推进，内部循环用于实际地将数组/向量的所有元素相加。

So the executions of the inner loop for the example above would be like this:

上面这个例子的内循环的执行是这样的:

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

Hope that helps.

希望有帮助。

#4

thisSum at your code line 8 is reset at beginning part of loop i,

在代码行8处的th问题在循环i的开始部分重置，

but thisSum in your loop j is keep adding the array a[ ] element in loop j.

但是循环j中的th问题是在循环j中不断添加一个[]元素。

Normally I will substitute value and assume value to understand how the loop work.

通常，我将替换value并假设value来理解循环是如何工作的。

Let assume vector a has 3 int elements 10,-20,100

假设向量a有3个int元素10 -20,100

therefore a.size() = 3

因此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

The concept of the function is it try to get the maximum sum by step by step remove the item from smallest index element to the largest index argument.

函数的概念是，它试图一步一步地获得最大和，将条目从最小的索引元素移到最大的索引参数。

1st loop i : maxSum = 90

第一个循环i: maxSum = 90

2nd loop i : maxSum = 90 (remove 10)

第二循环i: maxSum = 90(删除10)

3rd loop i : maxSum = 100 (remove 10,-20)

第3个循环i: maxSum = 100(删除10，-20)

#1