KarmaAndCoding: Dynamic Programming: Maximum Value Contiguous Subsequence.
Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.
Recurrence Equations:
For any i and j where (1 <= i < j <= n)
M(j) = Max sum over all windows ending at j.
M(j) = Max { M(j-1) + A[j], A[j] } ie either we extend the optimal window ending at j or start a fresh window with A[j].
Total time complexity: O(n) as there are n sub problems, each of size O(1).
Read full article from KarmaAndCoding: Dynamic Programming: Maximum Value Contiguous Subsequence.
No comments:
Post a Comment