e***s
发帖数: 799 | 1 Find the contiguous subarray within an array (containing at least one number
) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using
the divide and conquer approach, which is more subtle.
想知道O(nlogn)的解法。 | e***s
发帖数: 799 | | i**********e
发帖数: 1145 | 3 Programming pearls 上有。
二分后要考虑三种可能性：
１）max subarray 完全在左边某部分
２）max subarray 完全在右边某部分
３）两个 subarray 之间交接，左后边某部分和右前边某部分两个结合起来成为 max
subarray.
思路的突破就在于怎么在第三种状况下找出 max subarray. | e***s
发帖数: 799 | 4 靠，收到大牛回复，先膜拜一下！！
【在 i**********e 的大作中提到】
: Programming pearls 上有。
: 二分后要考虑三种可能性：
: １）max subarray 完全在左边某部分
: ２）max subarray 完全在右边某部分
: ３）两个 subarray 之间交接，左后边某部分和右前边某部分两个结合起来成为 max
: subarray.
: 思路的突破就在于怎么在第三种状况下找出 max subarray.
|
|
