3)给定n个整数（可能有负整数）组成的序列(a_1,a_2,…,a_n)，分别设计分治算法、动态规划算法，求该序列的子段(a_i,a_(i+1),…,a_j)，且该子段的和∑_(k=i)^j▒a_k 最大。

分治算法：
可以将序列分成左右两个部分，最大子段和可能在左半部分，右半部分或跨越中间的部分。因此，可以递归地求解三个部分的最大子段和，然后将它们合并。合并时，需要考虑跨越中间部分的情况，即从左半部分的某个位置向右扩展到右半部分的某个位置。

动态规划算法：
定义状态dp[i]表示以a[i]为结尾的最大子段和，因为最大子段和必须包含最后一个元素a[i]，所以对于dp[i]有两种情况：①最大子段和只包含a[i]；②最大子段和包含a[i]和前面的元素，即dp[i-1]+a[i]。因此，可以得到状态转移方程：dp[i] = max(a[i], dp[i-1]+a[i])。最终的结果是所有dp[i]中的最大值。

代码示例（使用动态规划算法）：

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

nums = [1, -2, 3, 5, -3, 2]
print(max_subarray(nums))  # 输出 8，即子段[3, 5]