The first step in solving this problem is to note that we can assume that at the beginning of each day, we sell all the stocks we own and start afresh (with however much money we have at that point). For example, if an investment strategy calls for buying 6 units of stock 2 on day 3 and selling them on day 6, we can form the following equivalent strategy:
* day 3: buy 6 units of stock 2 ; day 4: sell 6 units of stock 2
* day 4: buy 6 units of stock 2 ; day 5: sell 6 units of stock 2
* day 5: buy 6 units of stock 2 ; day 6: sell 6 units of stock 2
Once we have made this observation, it becomes clear that we can treat each day greedily: on each day, we want to maximize the return over the following night, subject to how much money we currently have to invest. But this is just the knapsack problem: for day d, stock s has cost PR_[s,d], and will yield profit PR[s,d+1]-PR[s,d]. So, for the first night, we can solve the knapsack problem and find out the maximum amount of money we can have at the beginning of day 2 after selling off our investment. Then this new amount of money becomes the size of the knapsack in the subsequent knapsack problem for the second night, and so on.
We have to solve O(D) knapsack problems, and each will take O(S*m) where m is the maximum amount of money we make. Thus the whole algorithm runs in O(D S m), which should run in time.
Code by Bruce Merry follows:
/*
PROG: stock
LANG: C++
*/
#include <fstream>
#include <algorithm>
using namespace std;
#define MAXS 51
#define MAXD 11
static int prices[MAXD][MAXS];
static int mout[500005];
int main()
{
ifstream in("stock.in");
ofstream out("stock.out");
int S, D, M;
in >> S >> D >> M;
for (int i = 0; i < S; i++)
for (int j = 0; j < D; j++)
in >> prices[j][i];
for (int i = 1; i < D; i++)
{
for (int j = 0; j <= M; j++)
mout[j] = j;
for (int s = 0; s < S; s++)
{
int p = prices[i - 1][s];
int po = prices[i][s];
for (int k = p; k <= M; k++)
{
int trg = mout[k - p] + po;
if (trg > mout[k]) mout[k] = trg;
}
}
M = mout[M];
}
out << M << "\n";
return 0;
}