最大子列和問題

給定N個(gè)整數(shù)的序列{A1, A2 ... An}，求函數(shù) f(i, j) = max{0, 從i到j(luò)An的最大值}

方法1：

遍歷所有可能的子序列，計(jì)算子序列的和

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

復(fù)雜度 O(N^3)

缺點(diǎn)：每次計(jì)算序列和都從頭到尾計(jì)算一次。實(shí)際上在i相同的時(shí)候，計(jì)算序列和只需要將當(dāng)前值加上前一個(gè)子序列和就好了。

由此優(yōu)化方法得到方法二。

方法2：

將當(dāng)前值加上一次的序列和作為當(dāng)前序列和。

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

上面的方法還可以繼續(xù)優(yōu)化：

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

增加要求

如果題目不光要求最大序列的和，而且要求給出最大子序列的開始與結(jié)束的下標(biāo)。

只要找對(duì)更新左端和右端的位置即可。如下：

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; // 暫時(shí)更新左端
    } else if (temp > sum) {
        sum = temp;
        right = i; // 更新右端
        left = templeft; // 更新左端
    }
}

我是誰？

我是iimT，大學(xué)生，技術(shù)宅，計(jì)算機(jī)科技愛好者，電音小王子。

我的博客：www.iimt.me

我在Weibo：@_iimT

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

想看到我的更多更新的話，很樂意你關(guān)注我！

你是誰？

歡迎在文后留下評(píng)論，一起討論，歡迎認(rèn)識(shí)新朋友。

如果你也有博客，在分享你的東西，歡迎交流、友鏈(本人博客底部可申請(qǐng))。

下一篇見~