给定一个数列，其中可能有正数也可能有负数，我们的任务是找出其中连续的一个子数列（允许空序列，空序列的和为0），使它们的和尽可能大。我们一起用多种方式，逐步优化解决这个问题。 数据范围 0 < n <= 100000使用C

首先，我们可以用暴力的方法来解决这个问题，枚举所有的子序列，求出它们的和，再从中选出最大的值。

时间复杂度为O(n^3)，代码实现如下：

#include <stdio.h>

int main()
{
    int n, a[100000], i, j, k, sum, max;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    max = 0;
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            sum = 0;
            for (k = i; k <= j; k++) {
                sum += a[k];
            }
            if (sum > max) {
                max = sum;
            }
        }
    }

    printf("%d\n", max);

    return 0;
}

接下来，我们可以用动态规划的方法来解决这个问题。我们定义一个状态dp[i]表示以a[i]结尾的子序列的最大和，如果dp[i-1]大于0，那么dp[i]就等于dp[i-1]+a[i]，否则dp[i]就等于a[i]。

时间复杂度为O(n)，代码实现如下：

#include <stdio.h>

int main()
{
    int n, a[100000], dp[100000], i, max;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    dp[0] = a[0];
    max = dp[0];
    for (i = 1; i < n; i++) {
        if (dp[i-1] > 0) {
            dp[i] = dp[i-1] + a[i];
        } else {
            dp[i] = a[i];
        }
        if (dp[i] > max) {
            max = dp[i];
        }
    }

    printf("%d\n", max);

    return 0;
}

最后，我们可以用分治的方法来解决这个问题。我们将数列分成左右两部分，分别求出左右两部分的最大子序列和，再求出跨越中间的最大子序列和，三者的最大值即为整个数列的最大子序列和。

时间复杂度为O(nlogn)，代码实现如下：

#include <stdio.h>

int max(int a, int b, int c)
{
    if (a >= b && a >= c) {
        return a;
    }
    if (b >= a && b >= c) {
        return b;
    }
    return c;
}

int max_subarray(int a[], int l, int r)
{
    if (l == r) {
        return a[l];
    }

    int m = (l + r) / 2;
    int left_max = max_subarray(a, l, m);
    int right_max = max_subarray(a, m+1, r);

    int i, left_sum = 0, left_max_sum = 0;
    for (i = m; i >= l; i--) {
        left_sum += a[i];
        if (left_sum > left_max_sum) {
            left_max_sum = left_sum;
        }
    }

    int right_sum = 0, right_max_sum = 0;
    for (i = m+1; i <= r; i++) {
        right_sum += a[i];
        if (right_sum > right_max_sum) {
            right_max_sum = right_sum;
        }
    }

    return max(left_max, right_max, left_max_sum+right_max_sum);
}

int main()
{
    int n, a[100000], i;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    printf("%d\n", max_subarray(a, 0, n-1));

    return 0;
}