Skip to main content
added 212 characters in body
Source Link
PKG
  • 1.5k
  • 10
  • 15

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

Update:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $[h_i \ldots h_j]$ for $1\leq i < j\leq n$,

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

Update:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $[h_i \ldots h_j]$ for $1\leq i < j\leq n$,

Source Link
PKG
  • 1.5k
  • 10
  • 15

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?