【PAT-Advanced】1007 Maximum Subsequence Sum

Problem

Given a sequence of $K$ integers ${ N_1, N_2, …, N_K }$. A continuous subsequence is defined to be ${ N_i, N_{i+1}, …, N_j }$ where $1≤i≤j≤K$. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer $K (≤10000)$. The second line contains $K$ numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices $i$ and $j$ (as shown by the sample case). If all the $K$ numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

Solution

这题怪坑的，过了好多次才完全过去。

题目是很经典的题目，最大子序列和，没记错的话是《数据结构与算法分析》第二章讨论了很久的一个问题。

稍稍整理一下几个经典的算法

算法一：疯狂穷举

最差但也是最简单最不需要动脑子的算法，先穷举子序列起点，再穷举子序列终点，然后求和。

复杂度是$N^3$

int MaxSubsequenceSum(const int A[], int N)
{
  int ThisSum, MaxSum;
  MaxSum = 0;
  //穷举A[i]
  for(int i=0; i<N; i++){
    //穷举A[j]
    for(int j=i; j<N; j++){
      ThisSum = 0;
      for(int k=i; k<=j; k++){
        //A[i] + ... + A[j]
        ThisSum += A[k];
      }
    }
    if(ThisSum > MaxSum){
      MaxSum = ThisSum;
    }
  }
  return MaxSum;
}

算法二：算法一的优化

类似算法一，先穷举起点再穷举终点，但在求和的部分对算法一进行优化。

复杂度是$N^2$

int MaxSubsequenceSum(const int A[], int N)
{
  int ThisSum, MaxSum;
  MaxSum = 0;
  //穷举A[i]
  for(int i=0; i<N; i++){
    ThisSum = 0;
    //穷举A[j]
    for(int j=i; j<N; j++){
        ThisSum += A[j];
    }
    if(ThisSum > MaxSum){
      MaxSum = ThisSum;
    }
  }
  return MaxSum;
}

算法三：分治

用递归进行分治，把整个序列分成左右两半，整个序列的最大子序列和可能有三种情况，一种是左半个序列的最大子序列和，一种是右半个序列的最大子序列和，另一种是横跨中间分界线。分别计算这三种的最大和，再取其中最大值即可。前两种直接递归可以算出来，第三种，在左半个中求包含右边界的最大和，在右半个中求包含左边界的最大和，两者相加即可。

复杂度是$NlogN$

static int MaxSubSum(const int A[], int left, int right)
{
  int MaxLeftSum, MaxRightSum;
  int MaxLeftBorderSum, MaxRightBorderSum;
  int LeftBorderSum, RightBorderSum;
  int center;
  if(left == right){
    if(A[left] > 0){
      return A[left];
    }else{
      return 0;
    }
  }
  center = (left + right) / 2;
  //递归求左右两半的最大子序列和
  MaxLeftSum = MaxSubSum(A, left, center);
  MaxRightSum = MaxSubSum(A, center+1, right);
  //求左半部分中包含右边界的最大和
  for(int i=center; i>=left; i--){
    LeftBorderSum += A[i];
    if(LeftBorderSum > MaxLeftBorderSum){
      MaxLeftBorderSum = LeftBorderSum;
    }
  }
  //求右半部分中包含左边界的最大和
  for(int i=center+1; i<=right; i++){
    LeftBorderSum += A[i];
    if(RightBorderSum > MaxRightBorderSum){
      MaxRightBorderSum = RightBorderSum;
    }
  }
  return max(MaxLeftBorderSum+MaxRightBorderSum, MaxLeftSum, MaxRightSum);
}

int MaxSubsequenceSum(const int A[], int N){
  return MaxSubSum(A, 0, N-1);
}

算法四：动态规划

一个比较取巧的优秀算法，当遇到一部分和小于零就舍弃，这样就只要进行一次遍历。

后来才发现这有点动态规划的意思，如果用dp[i]存以A[i]结尾的子序列的最大和，则dp[i+1] = max(dp[i]+A[i+1], A[i+1])，简化完大概就是如果dp[i]<0就不要了酱紫。具体看代码。

复杂度是$N$

int MaxSubsequenceSum(const int A[], int N){
  int thisSum, maxSum;
  thisSum = maxSum = 0;
  for(int j=0; j<N; j++){
    thisSum += A[j];
    if(thisSum > maxSum){
      maxSum = thisSum;
    }else if(thisSum < 0){
      thisSum = 0
    }
  }
  return maxSum;
}

然后说一下遇到的坑

手动划重点：If all the $K$ numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
如果是0+全负，类似于-1 0 -3 -2这样，要输出0 0 0
可以参考一下前人避雷经验

下面贴代码

#include <bits/stdc++.h>
using namespace std;

#define MAXN 10005

int K;
int num[MAXN];
int maxsum = 0;
int first, last;
int tempf, templ;
bool zero = false;

int main(int argc, const char * argv[]) {
    cin >> K;
    for(int i=0; i<K; i++){
        cin >> num[i];
    }
    if(K == 0){
        maxsum = 0;
    }
    int sum = 0;
    for(int i=0; i<K; i++){
        if(num[i] == 0){
            zero = true;
        }
        sum += num[i];
        if(sum > maxsum){
            maxsum = sum;
            first = tempf;
            templ = last = i;
        }else if (sum < 0){
            sum = 0;
            tempf = templ = i+1;
        }else{
            templ = i;
        }
    }
    if(maxsum <= 0){
        if(zero){
            cout << "0 0 0" << endl;
        }else{
            cout << 0 << " " << num[0] << " " << num[K-1] << endl;
        }
    }else{
        cout << maxsum << " " << num[first] << " " << num[last] << endl;
    }
    return 0;
}