2、构性质,并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。(提示:令)解:1)分析按照第一章,列出步数统计表,计算可得2)分治算法:将所给的序列a[1:n]分为两段a[1:n/2]、a[n/2+1:n],分别求出这两段的最大子段和,则a[1:n]的最大子段和有三种可能:①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同;②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同;③a[1:n]的最大子段和为两部分的字段和组成,即;intMaxSubSum(int*a,intleft,intright){ i