Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
the contiguous subarray
[−2,1,−3,4,−1,2,1,−5,4]
,the contiguous subarray
[4,−1,2,1]
has the largest sum = 6
.
More practice:
O(n) solution
divide and conquer version O(nlogn)
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Solution: classic algorithm problem for introducing dynamic programming. Check wiki to get the detailed explanation.
Comments
Post a Comment