本文介绍了子序列在整型数组最大总和的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
由于整数数组,你怎么能找到两个指数,i和j,使得在子数组起始元素的总和,并在指数结束最大化,线性时间?
Given an array of integers, how can you find two indices, i and j, such that the sum of the elements in the subarray starting and ending at the indices is maximized, in linear time?
推荐答案
从我的编程珍珠的:
maxsofar = 0
maxendinghere = 0
for i = [0, n)
/* invariant: maxendinghere and maxsofar are accurate
are accurate for x[0..i-1] */
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
这篇关于子序列在整型数组最大总和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!