给定由n个数组成的序列a1，a2，……，an，序列中可能有负数，要在这n个数中选取相邻的一段ai， ai+1，……，aj（1≤i≤j≤n）使其和最大，并输出最大的和。当所有的数均为负数时，定义最大子段和为0。其中数据个数n和n个数据都通过键盘输入，要求使用动态规划算法实现。

这是一个经典的最大子段和问题，可以使用Kadane算法或者动态规划算法来解决。动态规划算法的时间复杂度为O(n)，具体实现可以参考以下伪代码：

max_sum = 0
cur_sum = 0
for i in range(n):
cur_sum = max(cur_sum + a[i], 0)
max_sum = max(max_sum, cur_sum)
print(max_sum)

其中，cur_sum表示以当前位置为结尾的最大子段和，max_sum表示全局最大子段和。如果当前位置的数加上前面的最大子段和cur_sum为负数，则表示当前位置作为起点的最大子段和不能包含前面的数，cur_sum需要被重新赋值为0，从当前位置开始重新计算最大子段和。最终输出全局最大子段和即可。