已知一个整数序列，求其和最大的最长连续子序列。请你帮我分别设计三种代码。第一种算法时间复杂度不高于O(n**3），第二种算法时间复杂度不高于O（n**2），第三种算法时间复杂度为O（n））

第一种算法：

暴力枚举所有可能的子序列，计算它们的和并比较得出最大值。时间复杂度为O(n**3)。

代码如下：

def max_subarray(nums):
    n = len(nums)
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            curr_sum = sum(nums[i:j+1])
            if curr_sum > max_sum:
                max_sum = curr_sum
    return max_sum

第二种算法：

使用动态规划，定义状态dp[i]为以第i个元素结尾的最大子序和。状态转移方程为dp[i] = max(dp[i-1]+nums[i], nums[i])。时间复杂度为O(n**2)。

代码如下：

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)。

代码如下：

def max_subarray(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    mid = n // 2
    left_max = max_subarray(nums[:mid])
    right_max = max_subarray(nums[mid:])
    cross_max = max_cross_subarray(nums, mid)
    return max(left_max, right_max, cross_max)

def max_cross_subarray(nums, mid):
    left_sum = float('-inf')
    curr_sum = 0
    for i in range(mid-1, -1, -1):
        curr_sum += nums[i]
        if curr_sum > left_sum:
            left_sum = curr_sum
    right_sum = float('-inf')
    curr_sum = 0
    for i in range(mid, len(nums)):
        curr_sum += nums[i]
        if curr_sum > right_sum:
            right_sum = curr_sum
    return left_sum + right_sum