Maximum Subarray
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.
思路:
根据Wikipedia,这是Brown大学某教授给学生的一道练习题。之后被CMU某教授找到O(n)的解法。
这个解法的思路很简单。设两个变量,一个是如果以当前元素为最长子数组的最后一个元素,所能达到的最大值max_ending_here。另一个是已知的最大值max_so_far。
其实是一个动态......
阅读全文