문제 설명
제거 방법 : java.lang.OutOfMemoryError (how to remove : java.lang.OutOfMemoryError)
이 질문을 해결하고 있습니다(아래에 솔루션(dp 포함)에 대해 설명). java.lang.OutOfMemoryError 오류가 발생합니다. dp가 불필요한 계산을 제거한다는 것을 배웠으므로 dp도 적용했지만 왜 이 오류가 발생하여 dp보다 최적화할 수 있습니까? 또는 솔루션이 작은 입력에 대해 실행될 때 내가 뭔가 잘못하고 있습니까?
문제 설명
귀하의 알고리즘은 시장을 예측하는 데 너무 능숙해져서 이제 Wooden Orange Toothpicks Inc.(WOT)의 주가가 얼마인지 알 수 있습니다. 다음 N일 동안 진행됩니다.
매일 WOT 주식 1주를 사거나 소유하고 있는 WOT 주식을 얼마든지 팔거나 거래를 하지 않을 수 있습니다. 최적의 거래 전략으로 얻을 수 있는 최대 이익은 얼마입니까?
참조 솔루션
방법 1:
As mention in the comment, for your dp table, you are using 50000*50000*64 bit memory (long[][]dp), which is around 20 GB, and it is too large for any personal computer.
The problem can be solved in a much easier manner.
For set of n days, assume that in day i, we have the largest price for WOT, so, to make the largest profit, we need to buy WOT from day 0 to day i ‑ 1, and sell all of them in day i. From day i + 1 onward, we can follow the same strategy, which we will result us the maximum profit.
Space complexity for this solution is O(n), and time complexity is O(n log n) if implemented properly.
Pseudo‑code:
class WOT{
int day;
int price;
}
WOT[]data = new WOT[n];
//Initialize data here
long[]cost = new long[n];
for(int i = 0; i < n; i++)
cost[i] = data[i].price + (i > 0 ? cost[i ‑ 1] : 0);
sort data based on price
int startDate = 0;
long result = 0;
for(int i = n ‑ 1; i >= 0; i‑‑){
if(data[i].day > startDate){
int numberOfDays = data[i].day ‑ startDate;
result += numberOfDays*data[i].price ‑ (cost[data[i].day ‑ 1] ‑ cost[startDate ‑ 1])
startDate = data[i].day + 1;
}
}
print result;
(by JSONParser、Pham Trung)