Dynamic Programming & Maximizing Profit Buying & Selling Items Programing Exercise

I’m working on a algorithms & data structures multi-part question and need an explanation to help me learn.

Instructions say this should not take more than one hour. This is time sensitive and MUST be done today.

This must be solved using dynamic programming and the solution MUST include

1. A definition of subproblems

2. A recursion, including a base case

3. A bound on the number of subproblems (for example: the number of subproblems isO(n^2k))

4. A bound on the recursion time (for example: the recursion takes timeO(n))

Maximize algorithm speed. Unless explicitly stated otherwise, pseudocode and examples are not required.

In this particular case we want to maximize profit and print the sequence of purchases that maximizes profit.