c++ - 有人可以用 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;
}

我想知道是否有人可以解释该算法是如何工作的？我擅长 for 循环，我只是不擅长嵌套循环。每次第 8 行的外部 for 循环运行时，“thisSum”总是 0 还是静态的？

非常感谢!我真的很努力去理解这个算法。请帮我!我非常感谢您付出的时间和精力。

Answer 1

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

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

如果 maxSum 高于它已经包含的值，则外层循环将其替换为 thisSum。

所以如果 vector 包含:

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 将为 false，因此不会更改它。在第 4 次迭代中，6 > 4，因此它会将 maxSum 设置为 6。最后一次迭代不会改变它。最后，它将返回 6。