0

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

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 还是静态的？

非常感谢！我正在努力理解算法。请帮我！我真的很感激时间和精力。

4

4 回答 4

2

外部循环遍历 vector 的每个元素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将为 false，因此不会更改它。在第 4 次迭代中，6 > 4，因此它将设置maxSum为6。最后一次迭代不会改变它。最后，它会返回6。

于 2015-01-09T01:17:05.800 回答
0

您的代码第 8 行的 thisSum 在循环i的开始部分被重置，

但是循环 j 中的 thisSum 会继续在循环 j 中添加数组a [ ]元素。

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

假设向量 a 有 3 个 int 元素 10,-2​​0,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

该函数的概念是它尝试从最小索引元素到最大索引参数逐步删除项目，以获得最大总和。

第一个循环 i：maxSum = 90

第二个循环 i：maxSum = 90（删除 10）

第三个循环 i : maxSum = 100 (删除 10,-2​​0)

于 2015-01-09T01:59:37.463 回答
0

示例 a = [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

希望有帮助。

于 2015-01-09T01:23:10.967 回答
0

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.

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.

于 2015-01-09T01:15:47.317 回答