PHP-php查找和最大的连续子串

PHP-php查找和最大的连续子串

灵芸 发布于 2017-06-11 字数 90 浏览 1083 回复 2

给定一个字串数组$arr = array{-3,5,2,1,7,-9,5,3,23,-111,3,7},要求时间复杂度为O(n)。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

灵芸 2017-08-03 1 楼

可以使用动态规划的方法进行求解,首先建立状态方程。
设b[j]表示第j处,以arr[j] 结尾的子序列的最大和,则

b[j] = max(a[j] + b[j-1] , a[j]);

而我们的所求的答案,就是从1- n对b数组求最大值。
具体的实现代码可以参考一下这个:动态规划法解决最大连续子序列和