算法分析系列文章中的代码可被任何人无偿使用于任何场景且无需注明来源也不必在使用前征得本文作者同意。
算法分析系列文章旨在传播准确、完整、简洁、易懂、规范的代码实现,并传授基本的编程思想和良好的编码习惯与技巧。
若文章中的代码存在问题或逻辑错误,请通过邮件等形式(见文章结尾)告知于本文作者以便及时修正错误或改进代码。
算法系列文章不可避免地会参考和学习众多网友的成果,在行文风格、内容及求解思路上也会进行借鉴,如有侵权嫌疑,请联系本文作者。
PS:若为转载该文章,请务必注明来源,本站点欢迎大家转载。
问题描述
给定一个整数(正负数不限)序列 $a_1, a_2, a_3, …, a_n$ ,从该序列中选取任意相邻的一段求和(简称为「子段和」),求解该序列的最大子段和。注:若整个序列的所有元素均为负数,则其最大子段和固定为0。
例如,序列[64, -24, 88, -39, -54, 16]
的最大子段和为128
(= 64 + (-24) + 88
)。