Maximum value of a contiguous subsequence.
This problem is only interesting if there are -ve values in the array. We can solve this problem in linear time using Dynamic Programming. There are O(N) subproblems each taking O(1) time. The basic strategy is whenever a subsequence is found which has a -ve sum, the next subsequence can begin after the end of the subsequence which produced the -ve sum.
Code:
This problem is only interesting if there are -ve values in the array. We can solve this problem in linear time using Dynamic Programming. There are O(N) subproblems each taking O(1) time. The basic strategy is whenever a subsequence is found which has a -ve sum, the next subsequence can begin after the end of the subsequence which produced the -ve sum.
Code:
No comments:
Post a Comment