题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

选取 [3, 5] 子段 {3, -1, 2}，其和为 4。

题解

1. 分治法

时间复杂度 O(n*log n)，空间复杂度 O(n)

经过分析，发现最大子序列和可能在三处出现。

• 出现在输入数据的左半部分- 出现在输入数据的右半部分
• 跨越输入数据的中间元素，从而占据左右两半部分

前两种情况可以递归求解。第三种情况的最大和可以通过求出前半部分的最大和（包括前半部分的最后一个元素）以及后半部分的最大和（包括后半部分的第一个元素），再将两部分相加得到。

#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int tripleMax(const int a, const int b, const int c);
int MaxSubSum(const int *a, const int begin, const int end);

int main() {
  int n, i;
  scanf("%d", &n);
  int *a = (int *)malloc(n * sizeof(int));
  for (i = 0; i < n; i++)
    scanf("%d", a + i);

  printf("%d", MaxSubSum(a, 0, n - 1));
  free(a);
  return 0;
}

int tripleMax(const int a, const int b, const int c) {
  if (a >= b && a >= c)
    return a;
  else if (b >= a && b >= c)
    return b;
  else
    return c;
}

int MaxSubSum(const int *a, const int begin, const int end) {
  int m = (begin + end) >> 1, i;
  int leftBorderSum = a[m], rightBorderSum = a[m + 1];
  int maxLeftBorderSum = a[m], maxRightBorderSum = a[m + 1];

  if (begin == end)
    return a[begin];

  int maxLeftSum = MaxSubSum(a, begin, m);
  int maxRightSum = MaxSubSum(a, m + 1, end);

  for (i = m - 1; i >= begin; i--) {
    leftBorderSum += a[i];
    maxLeftBorderSum = MAX(leftBorderSum, maxLeftBorderSum);
  }

  for (i = m + 2; i <= end; i++) {
    rightBorderSum += a[i];
    maxRightBorderSum = MAX(rightBorderSum, maxRightBorderSum);
  }

  return tripleMax(maxLeftSum, maxRightSum,
                   maxLeftBorderSum + maxRightBorderSum);
}

2. 贪心法

时间复杂度 O(n)，空间复杂度 O(1)

用 f(i) 代表以第 i 个数结尾的连续子数组的最大和，则有
f(i) = max(a[i], f(i- 1) + a[i])

#include <limits.h>
#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main() {
  int n, item, sum = 0, maxSum = INT_MIN;
  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {
    scanf("%d", &item);
    sum = MAX(sum + item, item);
    maxSum = MAX(sum, maxSum);
  }

  printf("%d", maxSum);
  return 0;
}