邢城 发表于 2013-7-30 17:27:57

[google面试题]Given
 an
 array,
describe
 an 
algorithm
 to
 identify
 the
 subarray
 with
 the 
maximum
 sum.

For example,if the input is,the output would be.

孙宏雷 发表于 2013-7-30 17:53:33

Good Answer:Observe that the sum of a subarray from element i to element j isequal to the sum of the subarray from element 1 to element j minus the subarrayfrom element 1 to element i‐1.Our algorithm will iterate through the array.Thealgorithm keeps track of the sum x of the elements no later than the element.It willalso keep track of the minimum sum y of the subarray from the first element to anelement no later than the current element.Finally,It will also keep track of thesubarray z with the maximum sum so far.A teach step,we update x by adding thecurrent element to it.We updatey by checking whether x<y; if so, we set y to be x.We update z by checking whether y‐x is greater than z;if so,we set z to be y‐x.For example,with the sample input,our algorithm would do thefollowing:Current element | x | y | z---------------------------------- 1 |1 | 0 | 1-3 | -2 | -2 | 0 5 |3 | -2 | 5-2 | 1 | -2 | 5 9 |10 | -2 | 12-8 | 2 | -2 | 12-6 | -4 | -4 | 12 4 |0 | -4 | 1
页: [1]
查看完整版本: [google面试题]Given
 an
 array,
describe
 an 
algorithm
 to
 identify
 the
 subarray
 with
 the 
maximum
 sum.