给定一个数列，其中可能有正数也可能有负数，我们的任务是找出其中连续的一个子数列（允许空序列，空序列的和为0），使它们的和尽可能大。我们一起用多种方式，逐步优化解决这个问题。 数据范围 0 < n <= 100000 输入 第一行一个数n，表示数列的长度 接下来n行，每行一个数，表示数列的具体数值 输出 一个数，最大连续子序列和

这个问题可以使用分治、动态规划和贪心算法来解决，下面我分别介绍一下。

## 方法一：分治法

我们可以将原问题分解成两个子问题：

1. 找出数列的中间位置 $mid$，分别求出左边和右边的最大连续子序列和；
2. 找出跨越中间位置的最大连续子序列和。

对于第一步，我们可以使用递归来求解。对于第二步，我们可以从中间位置开始，向左和向右分别扫描，求出左边和右边的最大连续子序列和，然后将它们加起来即可。

下面是使用 Python 实现的代码：

def maxSubArray(nums, left, right):
    if left == right:
        return nums[left]

    mid = (left + right) // 2
    leftMax = maxSubArray(nums, left, mid)
    rightMax = maxSubArray(nums, mid+1, right)

    leftSum = nums[mid]
    curLeftMax = nums[mid]
    for i in range(mid-1, left-1, -1):
        leftSum += nums[i]
        curLeftMax = max(curLeftMax, leftSum)

    rightSum = nums[mid+1]
    curRightMax = nums[mid+1]
    for i in range(mid+2, right+1):
        rightSum += nums[i]
        curRightMax = max(curRightMax, rightSum)

    return max(leftMax, rightMax, curLeftMax+curRightMax)
    
n = int(input())
nums = []
for i in range(n):
    nums.append(int(input()))
print(maxSubArray(nums, 0, n-1))

## 方法二：动态规划

我们定义 $dp[i]$ 表示以 $nums[i]$ 结尾的最大连续子序列和。

显然，当 $i=0$ 时，$dp[0]=nums[0]$。

当 $i>0$ 时，$dp[i]$ 的值可以由以下两种情况转移而来：

1. $dp[i-1]+nums[i]$：将 $nums[i]$ 加入到以 $nums[i-1]$ 结尾的最大连续子序列中；
2. $nums[i]$：以 $nums[i]$ 作为新的最大连续子序列的起点。

因此，$dp[i]$ 的值为上述两种情况中的较大值，即：

$$dp[i] = \max(dp[i-1]+nums[i], nums[i])$$

最终的答案为 $dp$ 数组中的最大值。

下面是使用 Python 实现的代码：

n = int(input())
nums = []
for i in range(n):
    nums.append(int(input()))

dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
    dp[i] = max(dp[i-1]+nums[i], nums[i])

print(max(dp))

## 方法三：贪心法

我们从左到右遍历整个数列，对于每个元素，维护两个变量：

1. $curSum$：当前的最大连续子序列和；
2. $maxSum$：遍历过的所有子序列中的最大值。

初始时，$curSum$ 和 $maxSum$ 都设为 $0$。

对于每个元素 $nums[i]$，更新 $curSum$ 和 $maxSum$ 的过程如下：

1. 将 $nums[i]$ 加入 $curSum$；
2. 如果 $curSum$ 大于 $maxSum$，则更新 $maxSum$ 的值；
3. 如果 $curSum$ 小于 $0$，则将 $curSum$ 设为 $0$。

遍历结束后，$maxSum$ 的值即为最大连续子序列和。

下面是使用 Python 实现的代码：

n = int(input())
nums = []
for i in range(n):
    nums.append(int(input()))

curSum = 0
maxSum = float('-inf')
for num in nums:
    curSum += num
    maxSum = max(maxSum, curSum)
    curSum = max(curSum, 0)

print(maxSum)

以上三种方法都可以解决这个问题，它们的时间复杂度分别为 $O(n \log n)$、$O(n)$ 和 $O(n)$，其中第三种方法最简单，也最快。