求解最大子序列和

tag： 數(shù)據(jù)結(jié)構(gòu)與算法

---

最大子序列和問題：

給定序列A ₁ , A ₂ ，... A _N ， 求最大的子序列和。
例如 ：
　　對于序列4, -3, 5, -2, -1, 2, 6, -2， 最大序列和為11（4 -3 + 5 - 2 - 1 + 2 + 6）

算法一：

利用兩個循環(huán)，第一個循環(huán)把序列遍歷一遍，第二個循環(huán)則從A _i 累加到A _N ，每加一次判斷一下是否大于之前的最大子序列和：

    
      int maxSubsequenceSum1 (const int arr[], int n) {
  int maxSum = 0;
  int temp;

  for (int i = 0; i < n; i++) {
    temp = 0;

    for (int j = i; j < n; j++) {
      temp += arr[j];
      if (temp > maxSum)
	maxSum = temp;
    }
  }

  return maxSum;
}
    
  

時間復(fù)雜度：O（n ² ）

算法二：

首先把序列從中間一分為二， 則最大子序列和的存在有三種情況：

1. 全在左邊的子序列
   
2. 全在右邊的子序列
   
3. 處在中間
   對于第一和第二種情況，只需要遞歸調(diào)用求解函數(shù)，對于第三種情況則要分別求出從中間出發(fā)，向左邊和向右邊各自的最大子序列和。

    
      int max(int a, int b, int c) {
  int max;

  if (a > b)
    max = a;
  else 
    max = b;

  if (c > max)
    max = c;

  return max;
}

int maxSubsequenceSum2 (const int arr[], int begin, int end) {
  int maxLeftSum, maxRightSum, maxLeftCenterSum, maxRightCenterSum, center, temp;

  if (begin >= end) {
    if (arr[begin] > 0)
      return arr[begin];
    else
      return 0;
  }

  center = (begin+end)/2;
  maxLeftSum = maxSubsequenceSum2(arr, begin, center);
  maxRightSum = maxSubsequenceSum2(arr, center+1, end);

  maxLeftCenterSum = 0;
  temp = 0;
  for (int i = center; i >= begin; i--) {
    temp += arr[i];

    if (temp > maxLeftCenterSum)
      maxLeftCenterSum = temp;
  }

  maxRightCenterSum = 0;
  temp = 0;
  for (int i = center+1; i <= end; i++) {
    temp += arr[i];

    if (temp > maxRightCenterSum)
      maxRightCenterSum = temp;
  }

  return max(maxLeftSum, maxRightSum, (maxLeftCenterSum+maxRightCenterSum));
}
    
  

時間復(fù)雜度:O(nlogn)

算法三:

累加序列,若發(fā)現(xiàn)當(dāng)前序列和大于之前最大序列和,則替換.若發(fā)現(xiàn)當(dāng)前序列和小于0,則將當(dāng)前序列和置換成0,相當(dāng)于把前面的序列都舍棄掉.

    
      int maxSubsequenceSum3(int arr[], int n) {
  int tempSum = 0, maxSum = 0;

  for (int i = 0; i < n; i++) {
    tempSum += arr[i];
    if (tempSum < 0)
      tempSum = 0;
    if (tempSum > maxSum)
      maxSum = tempSum;
  }

  return maxSum;    
}
    
  

時間復(fù)雜度:O(n)

逐步優(yōu)化求解最大子序列和