Dynamic programming calculates maximum retracement
define
Retracement is used to measure the fund’s ability to resist risk.
Maximum rollback definition
It is the extent by which the net worth of a product falls from its highest point to its lowest point over a given period of time.
The maximum retracement rate, not necessarily (peak-nadir net worth)/peak net worth, may occur during one of the periods of decline.
The formula can be expressed like this:
D is the net value of a day, I is the net value of a day, j is the net value of a day after I, Di is the net value of a day after Di, and Dj is the net value of a day after Di
Drawdown is the maximum retracement rate
Drawdown = Max ((di-dj) /Di) = Max (1-dj /Di); drawdown= Max ((di-DJ) /Di) = Max (1-dj /Di) The net value here is net value of answer authority commonly, because the net value after fund shares out bonus can drop, pure with unit net value calculation can appear forbear circumstance.
To calculate
Defines a data structure that contains a fallback interval and a maximum fallback value
public static class MaxWithdrawal {
/** * List of the largest rollback data */
private List<String> list;
/** * Maximum rollback value */
private String maxValue;
public List<String> getList(a) {
return list;
}
public String getMaxValue(a) {
returnmaxValue; }}Copy the codeDynamic programming, time complexity O (N), space complexity O (3N), three auxiliary arrays
/** * Dynamic programming to calculate the maximum retracement, according to the definition, the maximum retracement value is a negative number * D is the net value of a certain day, I is a certain day, j is a certain day after I, Di is the net value of the product on the I day, Drawdown = Max ((di-DJ) /Di), which is to evaluate the drawdown rate of each net value and find the maximum value. *@param list
* @return* /
public static MaxWithdrawal maxWithdrawalDp(List<String> list) {
if (Preconditions.isNullOrEmpty(list))
return null;
int size = list.size();
double[] dpMax = new double[size]; // define dpMax[I] as the maximum from 0 to I
dpMax[0] = NumberHelper.getDouble(list.get(0), 0);
double[] dpMin = new double[size]; // define dpMin[I] as the minimum from 0 to I
dpMin[0] = NumberHelper.getDouble(list.get(0), 0);
double[] dp = new double[size]; // define dp[I] as the maximum callback from 0 to I
dp[0] = 0;
int maxIndex = size -1;
int minIndex = 0;
int i = 0; // the I pointer tracks the maximum value
int j = 0; // the j pointer traces the minimum value
for (int k = 1; k< size; k++) {
if (NumberHelper.getDouble(list.get(k), 0) > dpMax[k-1]) {
dpMax[k] = NumberHelper.getDouble(list.get(k), 0);
i++;
j++;
maxIndex = k;
L.i("Dynamic gauge dpMax ["+k+"]:"+dpMax[k]);
} else {
dpMax[k] = dpMax[k-1];
}
if (NumberHelper.getDouble(list.get(k), 0) < dpMin[k-1]) {
dpMin[k] = NumberHelper.getDouble(list.get(k), 0);
j++;
minIndex = k;
L.i("Dynamic gauge dpMin ["+k+"]:"+dpMin[k]);
} else {
dpMin[k] = dpMin[k-1];
}
if (j > i) { // The minimum is meaningful after the maximum
//drawdown=(Di - Dj)/Di = 1 - Dj/Di
dp[k] = Math.max(1- dpMin[k] / dpMax[k], dp[k-1]);
L.i("Dynamic rules dp ["+k+"]:"+dp[k]);
} else {
dp[k] = dp[k-1];
}
}
L.i("Dynamic rules dp ["+(size-1) +"]:"+dp[size-1] + ",maxIndex:"+maxIndex+", minIndex:"+minIndex);
if (dp[size-1] = =0 || j == i || maxIndex >= minIndex) {
// Cannot find maximum retracement
return null;
}
MaxWithdrawal data = new MaxWithdrawal();
data.maxValue = NumberHelper.parsePercent(String.valueOf(dp[size-1]), "0.00%".2.true.false);
data.list = list.subList(maxIndex,minIndex+1);
return data;
}
Copy the codeCompressing arrays saves space
/** * Compressing arrays saves space **@param list
* @return* /
public static MaxWithdrawal maxWithdrawalDp2(List<String> list) {
if (Preconditions.isNullOrEmpty(list)) {
return null;
}
int size = list.size();
int i = 0; // the I pointer tracks the maximum value
int j = 0; // the j pointer traces the minimum value
int maxIndex = size - 1;
int minIndex = 0;
double dpMax = NumberHelper.getDouble(list.get(0), 0); // Current traversal maximum value
double dpMin = NumberHelper.getDouble(list.get(0), 0); // Minimum current traversal value
double dp = 0; // Calculate the current fallback value
for (int k = 1; k < size; k++) {
if (NumberHelper.getDouble(list.get(k), 0) > dpMax) {
dpMax = NumberHelper.getDouble(list.get(k), 0);
i++;
j++;
maxIndex = k;
}
if (NumberHelper.getDouble(list.get(k).getOriginRange(), 0) < dpMin) {
dpMin = NumberHelper.getDouble(list.get(k), 0);
j++;
minIndex = k;
}
if (j > i) {
dp = Math.max(1 - dpMin / dpMax, dp); //dp = (dpMax - dpMin) / dpMax}}if (j == i || minIndex <= maxIndex || dp == 0) {
return null;
}
MaxWithdrawal data = new MaxWithdrawal();
data.maxValue = NumberHelper.parsePercent(String.valueOf(dp), "0.00%".2.true.false);
data.list = list.subList(maxIndex, minIndex + 1);
return data;
}
Copy the codeIf you compute time complexity O (N^2) by definition, you generally don’t do it this way.