We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
@merovinjean 's solution is a perfect and out of this world solution. I have to trace to understand how it works. This is the Java port:
public static long InvestReturn(int i, int x, long[] prices, int num, long[][] jArr) {
if (i == num) {
jArr[num][x] = 0;
return 0;
}
if (jArr[i][x] != -1) {
return jArr[i][x];
}
long A = InvestReturn(i + 1, 1, prices, num, jArr);
long B = InvestReturn(i + 1, 0, prices, num, jArr);
A = A - B;
if (A - prices[i] > 0) { //buying one stock is optimal
jArr[i][x] = -prices[i] + A * (x + 1) + B;
return jArr[i][x];
} else { //selling all x stocks is optimal
jArr[i][x] = x * prices[i] + B;
return jArr[i][x];
}
}
public static long InvestReturn(long[] prices) {
long[][] jArr = new long[prices.length+1][2];
for (int i = 0; i < jArr.length; i++) {
jArr[i][0] = -1;
jArr[i][1] = -1;
}
return InvestReturn(0, 0, prices, prices.length, jArr);
}
I think it is equivalent to this:
public static long InvestReturn(long[] prices) {
long profitNowPlusMaxPrice = 0;
long profitNow = 0;
for (int i = prices.length - 1; i > -1; i--) {
long maxPrice = profitNowPlusMaxPrice - profitNow;
if (maxPrice > prices[i]) {
// buying is optimal
profitNowPlusMaxPrice = (maxPrice * (1 + 1)) - prices[i] + profitNow;
profitNow = (maxPrice * (0 + 1)) - prices[i] + profitNow;
} else {
// current price is max, replace max price
profitNowPlusMaxPrice = (1 * prices[i]) + profitNow;
profitNow = (0 * prices[i]) + profitNow;
}
}
return profitNow;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Stock Maximize
You are viewing a single comment's thread. Return to all comments →
@merovinjean 's solution is a perfect and out of this world solution. I have to trace to understand how it works. This is the Java port:
I think it is equivalent to this: