Max sum subsequence with non-consecutive elements – Kadane's Algorithm (DP) Posted on Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive. For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4]. First of all, lets solve the problem with less constraint. Suppose we need to find out max sum subarray. How we can do that efficiently? Kadane's Algorithm Its Kadane's max sum subarray problem. The algorithm basically scans the input array from left to right and calculates sum of the current subarray upto current position. If current sum is less than 0 then reset the sum to zero and thus starting a new subarray. While doing this it keeps the max sum. If current sum exceeds the max sum then we reset max sum to this sum and set the max sum subarray boundary. This is an O(n) solution. For example: A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=6 with the maxsum subarray [4, -1, 2, 1].
Read full article from Max sum subsequence with non-consecutive elements - Kadane's Algorithm (DP) - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment