最大子列和问题

给定N个整数的序列{A1, A2 ... An}，求函数 f(i, j) = max{0, 从i到jAn的最大值}

方法1：

遍历所有可能的子序列，计算子序列的和

int MaxSubSeqSum1 (int A[], int N) {
  int i, j, k, thisSum, maxSum = 0;
  for (i = 0; i < N; i++) {
    for (j = i; j < N; j++) {
      thisSum = 0;
      for (k = i; k <= j; k++) {
        thisSum += A[k];
      }
      if (thisSum > maxSum) {
        maxSum = thisSum;
      }
    }
  }
  return maxSum;
}

复杂度 O(N^3)

缺点：每次计算序列和都从头到尾计算一次。实际上在i相同的时候，计算序列和只需要将当前值加上前一个子序列和就好了。

由此优化方法得到方法二。

方法2：

将当前值加上一次的序列和作为当前序列和。

int MaxSubSeqSum2 (int A[], int N) {
  int i, j, k, thisSum, maxSum = 0;
  for (i = 0; i < N; i++) {
    for (j = i; j < N; j++) {
      thisSum = 0;
      for (k = i; k <= j; k++) {
        thisSum += A[k];
      }
      if (thisSum > maxSum) {
        maxSum = thisSum;
      }
    }
  }
  return maxSum;
}

上面的方法还可以继续优化：

方法3: 在线扫描

int MaxSubseqSum3 (int A[], int N) {
  int ThisSum = MaxSum = 0;
  
  for (int i = 0; i < N; i++) {
    ThisSum += A[i];
    
    if (ThisSum > MaxSum)
      MaxSum = ThisSum;
    else if (ThisSum < 0)
      ThisSum = 0;
  }
  
  return MaxSum;
}

增加要求

如果题目不光要求最大序列的和，而且要求给出最大子序列的开始与结束的下标。

只要找对更新左端和右端的位置即可。如下：

for (int i = 0; i < N; i++) {
    int templeft = -1;
    int left = -1, right = -1;
    cin >> tmp;
    A.push_back(tmp);
    temp += tmp;

    if (temp < 0) {
        temp = 0;
        templeft = i + 1; // 暂时更新左端
    } else if (temp > sum) {
        sum = temp;
        right = i; // 更新右端
        left = templeft; // 更新左端
    }
}

我是谁？

我是iimT，大学生，技术宅，计算机科技爱好者，电音小王子。

我的博客：www.iimt.me

我在Weibo：@_iimT

我在B站：https://space.bilibili.com/69824765/#/

想看到我的更多更新的话，很乐意你关注我！

你是谁？

欢迎在文后留下评论，一起讨论，欢迎认识新朋友。

如果你也有博客，在分享你的东西，欢迎交流、友链(本人博客底部可申请)。

下一篇见~