Maximum Subsequence sum with difference among consecutive numbers less than K – GeeksforGeeks

Given an array arr[], find the maximum sum that can be achieved by picking a subsequence such that the difference between consecutive elements in the subsequence is less than or equal to a given number ‘K’.

Examples:

Input: arr[] = {1, 8, 9, 4, 6, 7}, K = 2
Output: 24. 
Explanation: The maximum sum can be obtained by taking the subsequence {8, 9, 7}. As 8 + 9 + 7 = 24

Input: arr[] = {1, -2, 3, 14, 6, -17, 16, 25}, K = 5
Output: 30.
Explanation: The maximum sum can be obtained by taking the subsequence {14, 16}. As 14 + 16 = 30

Naive Approach: The Brute force approach to solve this problem is to generate all subsequences with no consecutive elements with differences greater than K. Then find the sum of all such subsequences and print the maximum sum. 

Time complexity: O(2ⁿ)
Auxiliary Space: O(1)

Efficient Approach: To solve the problem follow the below approach:

The idea to solve this problem is by using the concept of dynamic programming. In this approach, first, we initialize an array dp[] which stores the maximum sum ending at index i. Then we run a loop and for every index i, we have dp[i] as the sum of the current element arr[i] plus the maximum achievable sum in previous positions which has an absolute difference of less than or equal to k with arr[i].

Follow the steps involved in the approach:

• Initialize a vector say dp of the size of the array that will store the maximum sum till index i, dp[i].
• Initialize the base case, dp[0] with arr[0] as for a single element the maximum sum is the element itself.
• Run a loop from i = 1 to i < n.
• Initialize a variable say maxSum, that will store the maximum sum achievable so far.
• For each index i, run a loop from j = i – 1 to j ≥ 0 and check if the difference between the current element and the previous element is less than or equal to K, arr[i] – arr[j] ≤ K.
• If arr[i] – arr[j] ≤ K, update maxSum = max(maxSum, dp[j]). Here maxSum is the maximum sum achievable ending at the previous position.
• Update dp[i] with the maximum sum, dp[i] = maxSum + arr[i].
• In the last return the maximum element of the dp array which will be the maximum sum of subsequences with given conditions.

Below is the code for the above approach.

Time Complexity: O(N²)
Auxiliary Space: O(N)