Content deleted Content added
m Explanation on a confusing and undeveloped yet critical insight. |
|||
Line 112:
return max_so_far
</source>
'''Note:''' with a bit of reasoning you will see that <code>max_so_far</code> is equal to <math>\max(B_0, B_1, B_2, ..., B_i)</math>. In particular, with every iteration of <code>x<code>, we know that <code>max_ending_here</code> contains the sum of the largest subset right before <code>x<code>. <code>max_ending_here</code> will then contain the largest subset ending with <code>x<code>. The algorithm will then update <code>max_so_far</code> to be equal to the larger of <code>max_so_far</code> or <code>max_ending_here</code>. Thus, we wee that with every iteration of some element <code>x<code>, we find the largest subset that could end with <code>x<code>. Since we know that the largest subset has to end with an element in <code>A<code>, we have found the largest subset in <code>A<code>.
The algorithm can also be easily modified to keep track of the starting and ending indices of the maximum subarray (when <code>max_so_far</code> changes) as well as the case where we want to allow zero-length subarrays (with implicit sum 0) if all elements are negative.
| |||