Optimize Stock Trading - Coding in A Smart Way
Assume you are given an array P to indicate the prices of a stock yesterday from the opening to close time. If you can made one buy and afterward one sell, what is maximum return you can get? For example, if P = [5.78, 5.41, 7.5, 6.00, 7.19, 3.15, 7.36, 5.8, 4.62]. Then you should buy when the price is 3.15 and sell at 7.36. Thus, the return is (7.36 – 3.15) / 3.15 = 133.65%.
Actually, we can use dynamic programming to improve the program. Let M[i] be the maximum of the sub-array of P from i + 1. Then M[i] = max(M[i+1], P[i+1]). Remember to take care the last element of P. After we precompute the array M, then we can find the maximum return by looping through the array.
Read full article from Optimize Stock Trading - Coding in A Smart Way
Assume you are given an array P to indicate the prices of a stock yesterday from the opening to close time. If you can made one buy and afterward one sell, what is maximum return you can get? For example, if P = [5.78, 5.41, 7.5, 6.00, 7.19, 3.15, 7.36, 5.8, 4.62]. Then you should buy when the price is 3.15 and sell at 7.36. Thus, the return is (7.36 – 3.15) / 3.15 = 133.65%.
Actually, we can use dynamic programming to improve the program. Let M[i] be the maximum of the sub-array of P from i + 1. Then M[i] = max(M[i+1], P[i+1]). Remember to take care the last element of P. After we precompute the array M, then we can find the maximum return by looping through the array.
public static double maxReturn(double[] P){ //M[i] is the maximum of sub array of P from i + 1. double[] M = new double[P.length]; M[M.length - 1] = Double.NEGATIVE_INFINITY; for(int i = M.length - 2; i >= 0; i--) { M[i] = Math.max(M[i+1], P[i+1]); } double maxReturn = Double.NEGATIVE_INFINITY; for (int i = 0; i < M.length; i++) { double newReturn = (M[i] - P[i]) / P[i]; if (newReturn > maxReturn) { maxReturn = newReturn; } } return maxReturn;}