数组最大连续子序列和

数组的最大连续子序列和可以用动态规划算法来解决。

设 $dp[i]$ 表示以第 $i$ 个元素结尾的最大连续子序列和，则有以下状态转移方程：

$$
dp[i] = \begin{cases}
nums[i] & i = 0 \\
\max(dp[i-1]+nums[i], nums[i]) & i > 0
\end{cases}
$$

其中 $nums$ 是给定的整数数组。

最终的结果即为 $dp$ 数组中的最大值。

下面是 Python 代码实现：

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

时间复杂度为 $O(n)$。