标题: [google面试题]Given an array, describe an algorithm to identify the subarray with the maximum sum. [打印本页] 作者: 邢城 时间: 2013-7-30 17:27 标题: [google面试题]Given an array, describe an algorithm to identify the subarray with the maximum sum. For example,if the input is[1,‐3,5,‐2,9,‐8,-6,4],the output would be[5,‐2,9].作者: 孙宏雷 时间: 2013-7-30 17:53
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