最大m子段与总结及例题51nod1052、HDU1024如何求解？

本文共计1285个文字，预计阅读时间需要6分钟。

pythondef find_largest_segment_sum(a, m): n=len(a) max_sum=float('-inf') current_sum=0 count=0

for i in range(n): current_sum +=a[i] count +=1 if count > m or current_sum <=0: max_sum=max(max_sum, current_sum) current_sum=0 count=0

return max_sum

示例输入a=[-2, 1, -3, 4, -1, 2, 1, -5, 4]m=4

输出结果result=find_largest_segment_sum(a, m)print(最大的子段和为:, result)

最大m子段和

一、定义

给定由n个整数（可能为负）组成的序列a1、a2、a3...,an, 以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和最大！

特别注意：有些题目可能不存在负数答案，给出的序列全是负数，那么不管m是多少，答案是0。此时选择的子段是0个，不足m个，但符合题意。。。也可能有些题目要求，必须选够m个子段。区别在dp数组的初始化。前者要求dp初始为0，后者要求第0行为0，其余为负无穷

二、解题思路

动态规划，借助矩阵可以直观的看到计算过程。