擅长:python、mysql、java
<p>这个问题对我来说似乎很熟悉。。。快速搜索发现了一篇维基百科文章<a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow">Maximum subarray problem</a>。改编自本文中的c++解决方案</p>
<pre><code>def maxSubArray(seq):
max_so_far = seq[0]
max_ending_here = 0
begin = 0
begin_temp = 0
end = 0
for i in xrange(1, len(seq)):
if max_ending_here < 0:
max_ending_here = seq[i]
begin_temp = i
else:
max_ending_here += seq[i]
if max_ending_here >= max_so_far:
max_so_far = max_ending_here
begin = begin_temp
end = i
return max_so_far, begin, end
</code></pre>