Maximum sum subsequence with top down approach

general
1

Hello,
I am trying to solve the maximum sum subsequence problem, using topdown approach. I am able to come up with an O(n^3)
solution, but want an O(n^2) solution. The reason I’m not going with the bottom up approach (O(n^2)) is that I am fairly new to DP, and topdown approaches are really intuitive and much easier to come up with.

Here is the code(recursive). We can see that there are three different variables and hence we need to come up with a DP table like

dp[i][prev][sum]

int max_sum_sub(int arr[], int i, int n, int prev, int sum)
{
	// Base case: nothing is remaining
	if (i == n)
		return sum;

	// exclude the current element
	int exclude = max_sum_sub(arr, i + 1, n, prev, sum);

	// case 2: include the current element if it is greater
	// than previous element
	int include = sum;
	if (arr[i] > prev)
		incl = max_sum_sub(arr, i + 1, n, arr[i], sum + arr[i]);

	// return maximum of above two choices
	return max(incl, excl);
}

Please help.
Thanks

2

You can remove sum from the parameters if you build up the sum instead of passing it down, and you can use prev as an index rather than a value, which will give you the desired complexity of \mathcal{O}(n^2).

function f(i, prev):
    if i == 0:
        return 0
    exclude = f(i-1, prev)
    include = 0
    if A[i] < A[prev]:
        include = A[i] + f(i-1, i)
    return max(exclude, include)

Here A[1..n] are the elements of the array. Remember to set A[p] to a very large value before calling f(n, p). Normally I would choose p as n+1, but it can be anything outside 1..n. Hope this helps! :slight_smile:

3 Likes