arrays - qué - Encuentre precios de compra/venta en una variedad de valores de acciones para maximizar la diferencia positiva
valor de la empresa finanzas (23)
1. No podemos simplemente tomar la cantidad mínima entre los valores como "Best Buy" y la cantidad máxima como "Best Sell" porque "Sell" tiene que suceder después de "Buy".
2. No debemos tratar el mínimo registrado como la "Mejor compra" porque los días subsiguientes pueden tener valores de acciones cuya diferencia con el mínimo registrado puede generar ganancias que podrían ser menores que las "ganancias registradas".
3.Best Buy y Best Sell se tratan como una sola variante, ya que es la diferencia positiva entre estos valores la que produce el máximo beneficio.
4. Dado que cualquier mínimo registrado en el pasado es un posible candidato para la compra, la condición de beneficio máximo siempre se debe comparar con el mínimo registrado y el precio de las acciones del día actual. Por lo tanto, siempre debemos realizar un seguimiento del mínimo registrado, pero solo la presencia. El mínimo registrado no constituye "Best Buy" debido a la razón número 2.
Ahora tiene el siguiente código que se ejecuta en O (n) veces tendrá sentido.
public class BestStockBuyAndSell {
public static void main(String[] args) {
double[] stockPrices = {55.39,109.23,48.29,81.59,105.53,94.45,12.24};
int [] bestBuySellIndex = maxProfit(stockPrices);
System.out.println("Best Buy At "+stockPrices[bestBuySellIndex[0]]);
System.out.println("Best Sell At "+stockPrices[bestBuySellIndex[1]]);
System.out.println("Max Profit = "+(stockPrices[bestBuySellIndex[1]]-stockPrices[bestBuySellIndex[0]]));
}
public static int[] maxProfit(double[] stockPrices)
{
int bestBuy=0;
int bestSell=0;
int[] bestCombination ={bestBuy,bestSell};
double recordedMinimum = stockPrices[bestBuy];
int recordedMinimuIndex = bestBuy;
double bestProfitSofar = stockPrices[bestSell] - stockPrices[bestBuy];
for(int i=1;i<stockPrices.length;i++)
{
if(stockPrices[i] - recordedMinimum > bestProfitSofar)
{
bestProfitSofar = stockPrices[i] - recordedMinimum;
bestSell = i;
bestBuy = recordedMinimuIndex;
}
if(stockPrices[i] < recordedMinimum)
{
recordedMinimuIndex = i;
recordedMinimum = stockPrices[i];
}
}
bestCombination[0] = bestBuy;
bestCombination[1] = bestSell;
return bestCombination;
}
}
Recibí esta pregunta en una entrevista de hoy, y su solución optimizada me detuvo en seco (lo que me falla, porque realmente quería trabajar para esta compañía ...)
Dada una serie única de valores reales, cada uno de los cuales representa el valor de las acciones de una empresa después de un período de tiempo arbitrario, encuentra el mejor precio de compra y su correspondiente mejor precio de venta (comprar a bajo precio, vender alto).
Para ilustrar con un ejemplo, tomemos el indicador de acciones de la Compañía Z:
55.39 109.23 48.29 81.59 105.53 94.45 12.24
Es importante tener en cuenta el hecho de que la matriz está "ordenada" temporalmente, es decir, a medida que pasa el tiempo, los valores se agregan al extremo derecho de la matriz. Por lo tanto, nuestro valor de compra estará (debe estar) a la izquierda de nuestro valor de venta.
(En el ejemplo anterior, la solución ideal es comprar a 48.29 y vender a 105.53 )
Se me ocurrió la solución ingenua con la complejidad O (n 2 ) (implementada en java):
// returns a 2-element array: first element is the index in the argument array
// of the best buying price, and the second element is the index of the best
// selling price which, collectively, maximize the trading return
//
// if there is no favorable trading (e.g. prices monotonically fall), null is returned
public int[] maximizeReturn(ArrayList<Double> prices) {
int [] retval = new int[2];
int BUY = 0, SELL = 1;
retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
double difference = prices.get(j).doubleValue() -
prices.get(i).doubleValue();
if (difference > 0.0) {
if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() -
prices.get(retval[BUY]).doubleValue()) {
retval[BUY] = i;
retval[SELL] = j;
}
}
}
}
return (retval[BUY] > 0 ? retval : null);
}
Aquí es donde la cagué: hay una solución O (n) de tiempo lineal , y bombardeé por completo para intentar resolverlo (sí, lo sé, FALLO). ¿Alguien sabe cómo implementar la solución de tiempo lineal? (cualquier idioma con el que te sientas cómodo) ¡Gracias!
Editar
Supongo que, para cualquier persona interesada, recibí la noticia de que no obtuve el trabajo por el que entrevisté donde me hicieron esta pregunta. :(
Aquí está mi implementación O (n) para esto. Estoy usando una matriz de cambios para calcular el máximo beneficio y las fechas de compra y venta. Sus comentarios sobre esto son bienvenidos.
#include<stdafx.h>
#include<stdio.h>
int main()
{
//int arr[10] = {15, 3, 5,9,10,1,6,4,7,2};
int arr[7] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
int change[7];
int n=7;
for(int i=1;i<=n;i++)
{
change[i] = arr[i]- arr[i-1];
}
int i=0,index = 0;
int sum = 0;
int maxsum = 0;
int startpos = 0;
int endpos = 0;
while(index < n)
{
sum = sum + change[index];
if(maxsum < sum)
{
maxsum = sum;
startpos = i;
endpos = index;
}
else if (sum<0) // negative number ,set sum to zero
{
sum = 0;
i=index+1;
}
index++;
}
printf("max profit is%d %d %d", maxsum , startpos, endpos+1 );
}
Aquí está mi intento de usar Javascript. El script calcula la respuesta en O (N):
//Main Stock Array
var stock = [15, 20, 0, 3, 30, 45, 67, 92, 1, 4, 99];
//Setup initial variable state
var ans = {}, tmp = {}; //These are just for namespacing / syntatic sugar
ans.minVal = stock[0];
ans.minInd = 0;
ans.maxDiff = stock[1] - stock[0];
ans.maxInd = 1;
tmp.minInd = ans.minInd;
tmp.minVal = ans.minVal;
//Basically we iterate throught the array. If we find a new low, we start tracking it. Otherwise we compare the current index against the previously found low
for(i = 1; i <= stock.length-1; i++) {
if(tmp.minVal > stock[i]) {
tmp.minVal = stock[i];
tmp.minInd = i;
} else {
ans.diff = stock[i] - stock[tmp.minInd];
if(ans.diff > ans.maxDiff) { //Looks like we found a new maxDifference. Lets log the indexes
ans.maxDiff = ans.diff;
ans.maxInd = i;
ans.minInd = tmp.minInd;
ans.minVal = tmp.minVal;
}
}
}
document.write(''You should buy your stocks on day '' + ans.minInd + '' and sell on day '' + ans.maxInd);
Aquí está mi solución en Ruby:
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
max_diff = 0
diff = 0
min = values[0]
max = 0
values.each_with_index do |value, index = 1|
# get an array of the previous values before the current one
lag_values = values[0..index]
# get the minimum of those previous values
min_lag_value = lag_values.min
# difference between current value and minimum of previous ones
diff = values[index].to_i - min_lag_value.to_i
# if current difference is > previous max difference, then set new values for min, max_diff, and max
if diff > max_diff
max_diff = diff
min = min_lag_value
max = values[index]
end
end
min # => 48.29
max # => 105.3
max_diff # => 57
Aclamaciones
Aquí está mi solución, igual que @Doug T. excepto que también estoy haciendo un seguimiento del día en un índice. Por favor envíe sus comentarios.
int prices[] = {4,4,5,6,2,5,1,1};
//int prices[] = {100, 180, 260, 310, 40, 535, 695};
int currentBestSellPrice=0;
int currentBestBuyPrice=0;
int lowindex=0;
int highindex=0;
int low=prices[0];
int high=prices[0];
int profit=0;
int templowindex=0;
for(int i=0; i< prices.length;i++)
{
// buy low
if(prices[i] < low && i+1 < prices.length)
{
low = prices[i];
templowindex=i;
high=0;
}
// sell high
else if(prices[i] > high)
{
high = prices[i];
int potentialprofit = (high-low);
if(potentialprofit > profit)
{
profit = potentialprofit;
currentBestSellPrice = high;
currentBestBuyPrice = low;
highindex=i;
lowindex=templowindex;
}
}
}
System.out.println("Best Buy Price : "+ currentBestBuyPrice + " on day "+ lowindex);
System.out.println("Best Sell Price : "+ currentBestSellPrice+ " on day "+ highindex );
Aquí hay un intento (C ++). Básicamente, cada vez que hago un seguimiento de un nuevo tope, trato de ver si ese es el mejor beneficio hasta ahora. Sé que el "fondo" debe haber sido descubierto antes. En ese momento recuerdo la parte superior, la parte inferior y la ganancia máxima actual. Si se descubre un nuevo fondo más tarde, es DESPUÉS de la parte superior actual, por lo que debemos restablecer la parte superior y ver si una "parte superior" ligeramente más baja puede producir mejores ganancias.
#include <iostream>
int main()
{
double REALLY_BIG_NO = 1e99;
double bottom = REALLY_BIG_NO; // arbirtrary large number
double currBestBuy = 0.0;
double top = 0.0;
double currBestSell = 0.0;
double profit = 0.0;
// array of prices
double prices[] = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 152.0, 2, 170.0};
int numPrices = 10;// number of prices
for (int i = 0; i < numPrices; ++i)
{
if (prices[i] < bottom)
{
bottom = prices[i];
// reset the search on a new bottom
top = 0.0;
}
else if (prices[i] > top)
{
top = prices[i];
// calculate profit
double potentialProfit = (top - bottom);
if (potentialProfit > profit &&
bottom != REALLY_BIG_NO)
{
profit = potentialProfit;
currBestSell = top;
currBestBuy = bottom;
}
}
}
std::cout << "Best Buy: " << currBestBuy << "Best Sell: " << currBestSell << std::endl;
}
Hasta ahora he jugado con un montón de conjuntos de entrada diferentes, y hasta ahora no he tenido ningún problema ... (Avísame si pruebas esto y ves algo incorrecto)
Recomiendo encarecidamente utilizar la respuesta actualizada de Austin Salonen a esta pregunta y adaptarla a su idioma.
Aquí hay una solución javascript ...
function getMax(arr){
//we need more than at least 3 ints to be able to do this
if(arr.length <= 1) return arr;
// get the minimum price we can sell at to make a profit
var min = arr[0];
//get the first potential maximum profit
var max = arr[1] - arr[0];
//while looping through we must get a potential value,
//we can then compare that using the math.max using the maximum
//and the potential prices that we have seen. Once the loop runs the ouput here should be 6!
for(var i = 1; i < arr.length; ++i){
var current = arr[i];
var potential = current - min;
max = Math.max(max, potential);
min = Math.min(min, current);
}
return max;
}
console.log(getMax([10, 7, 5, 8, 11, 9]));
El tiempo de ejecución en esto es O (n)
Cía#:
static void Main(string[] args)
{
double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
for (int i = 1; i < values.Length; i++)
{
if (values[i] > values[i - 1])
{
//trending upward, append to existing differential
diff += values[i] - values[i - 1];
}
else
{
//trending downward, reset the diff
diff = 0;
}
if (diff > maxDiff)
{
maxDiff = diff;
max = values[i];
}
}
Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}
EDITAR : Nuevo algo basado en el caso de prueba fallido de @ Joe - Nice Catch BTW! También es la misma respuesta que la de @Doug T ahora ...
static void Main(string[] args)
{
double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };
double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
double bottom = values[0];
for (int i = 1; i < values.Length; i++)
{
diff += values[i] - values[i - 1];
if (diff > maxDiff)
{
maxDiff = diff;
max = values[i];
}
if (values[i] < bottom)
{
bottom = values[i];
diff = 0;
}
}
Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}
En mi esfuerzo por aprender Go, y también en mi cerebro en este, aquí está mi intento.
func GetMaxProfit2(prices []float64) (float64, float64) {
var min, max, pmin, pmax int
for i, v := range prices {
if v - prices[min] > prices[max] - prices[min] {
pmax = max
max = i
}
// Reset the max when min is updated.
if v < prices[min] {
pmin = min
min = i
pmax = max
max = i
}
}
// If min is ahead of max, reset the values back
if min >= max {
min = pmin
max = pmax
}
return prices[min], prices[max]
}
Esta es una solución C que realmente funciona:
void bestBuySell () {precios dobles [] = {10.50, 10.0, 3.0, 194.0, 55.39, 2.0, 109.23, 48.29, 81.59, 105.53, 94.45, 191.0, 200.0, 12.24}; int arrSize = 14; bestBuy doble = precios [0], bestSell = precios [1], bestPotentialBuy = precios [0]; doble potencialProfit = precios [1] - precios [0];
for(int i = 1; i < (arrSize-1); i++)
{
if(prices[i] < bestBuy)
bestPotentialBuy = prices[i];
if((prices[i+1] - bestPotentialBuy) > potentialProfit)
{
bestBuy = bestPotentialBuy;
bestSell = prices[i+1];
potentialProfit = prices[i+1] - bestPotentialBuy;
}
}
printf( "bestBuy %f bestSell %f/n", bestBuy, bestSell );
}
F # solución para aquellos que estén interesados en lo funcional. No diría que sea muy diferente.
let start, _, profit =
[55.39; 109.23; 48.29; 81.59; 81.58; 105.53; 94.45; 12.24 ]
|> Seq.fold (fun (start,newStart,profit) i ->
let start = defaultArg start i
let newStart = defaultArg newStart i
let newProfit = i - newStart
if profit < newProfit
then Some newStart, Some newStart,newProfit
else if start > i
then Some start, Some i, profit
else Some start,Some newStart,profit) (None,None, 0.0)
printf "Best buy: %f; Best sell: %f" start.Value (start.Value + profit)
Salida:
Best buy: 48.290000; Best sell: 105.530000
La forma en que lo pensé fue que, para cada índice i ¿cuál sería el índice ideal para vender estas acciones? Esto es, por supuesto, el índice del valor máximo después de i . Esto reduce nuestro problema para encontrar el elemento máximo después del índice i para cada i en [1 ... n] Si pudiéramos hacerlo en O(n) , entonces podríamos encontrar la mejor opción entre ellos e informarlos.
Una forma de hacer esto es comenzar a atravesar desde el final de la matriz, manteniendo dos variables, una para guardar el elemento más grande que hemos encontrado hasta ahora max_till_now y otra para guardar la ganancia máxima que podríamos obtener hasta ahora, la profit . Esto es solo para que podamos hacer esto en una sola pasada. También podríamos usar espacio adicional y, para cada elemento i , almacenar el índice del elemento más grande en el rango [i + 1 ... n] para él y luego encontrar el beneficio máximo.
Aquí está mi código de python:
def buyLowSellHigh(L):
length = len(L)
profit = 0
max_till_now = L[length - 1]
for i in xrange(length - 2, -1, -1):
if L[i] > max_till_now: max_till_now = L[i]
else:
if max_till_now - L[i] > profit: profit = max_till_now - L[i]
return profit
La idea es simple. Mantener dos punteros, lo y hola.
Hacer un loop de foor
- Si el precio es más alto que hola, actualice hi = precio, continúe
- Si el precio es más bajo que hola. Entonces lo y hola es uno de los posibles candidatos. Calcule la ganancia, guárdela si es más grande que las ganancias anteriores y reinicie lo, hola al precio
def getBestProfit(prices):
lo = hi = profit = 0
for price in prices:
if lo == 0 and hi == 0:
lo = hi = price
if price > hi:
hi = price
if price < low:
tmpProfit = hi - lo
if tmpProfit > profit:
profit = tmpProfit
lo = hi = price
return profit
Eso es
Me gustaría describir cómo abordé este problema para facilitar la comprensión de mi código:
(1) Por cada día, si tuviera que vender mis acciones ese día, ¿cuál sería la cantidad mínima que podría haber pagado para comprarlas? Esencialmente, estoy haciendo un seguimiento del precio mínimo antes de ese día
(2) Por cada día, si tuviera que vender ese día, ¿cuánto estoy ganando? (Precio de las acciones en ese día - precio mínimo)
Esto demuestra que tengo que hacer un seguimiento de dos cosas: (1) el precio mínimo de las acciones hasta ahora (2) la mejor ganancia hasta ahora.
El problema se convierte en elegir qué día vender. Venderé el día que me dé la mejor ganancia. Aquí está mi código de Java:
public static void findBestDeal(double [] stocks) {
double minsofar = stocks[0];
double bestsofar = 0.0;
for(int i=1; i< stocks.length; i++) {
// What is the cheapest price to buy it if I''m going to sell it today
if(stocks[i-1] < minsofar) {
minsofar = stocks[i-1];
}
// How much do I earn if I sell it on ith day?
double current_deal = stocks[i] - minsofar;
// Is selling today better?
if(current_deal > bestsofar) {
bestsofar = current_deal;
}
}
System.out.println("Found the best deal: " + bestsofar + " (Bought at " + minsofar + " and sold at " + (minsofar+bestsofar) + ")");
}
Otra solución de Ruby:
# Here''s some examples. Please feel free to give your new test.
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
# values = [5, 6, 4, 7, 9, 8, 8]
# values = [5, 10, 4, 6, 7]
# values = [5, 10, 4, 6, 12]
# values = [1, 2, 3, 4, 5]
# Initialize parameters.
min = values[0]
best_buy_time = values[0]
best_sell_time = values[0]
max_profit = 0
# This solution is based on comparing previous k elements and k+1 one.
# The runtime is O(n) and it only use O(1) auxiliary storage.
values.each_with_index do |value, index = 1|
# Check value in this turn.
puts value
# Check current value is bigger than min or not.
# If not, we find the new min.
if value <= min
min = value
# If current value is bigger than min and
# (value - min) is bigger than previous max_profit,
# set new best_buy_time, best_sell_time & max_profit.
else
if value - min >= max_profit
best_buy_time = min
best_sell_time = value
max_profit = value - min
end
end
end
# Let''s see about the result.
puts "/nbest_buy_time: ", best_buy_time, "/nbest_sell_time: ", best_sell_time, "/nmax_profit: ", max_profit
Realmente tengo que señalar como una pregunta de entrevista que espera que usted la resuelva ya que O (n) es totalmente absurdo. Las preguntas de la entrevista están destinadas a demostrar que puede resolver un problema, y usted pudo resolverlo. El hecho de que lo resolvieras en O (N ^ 2) vs O (N) debería ser irrelevante. Si una empresa dejara de contratarlo por no resolver esto en O (N), probablemente no sea una empresa en la que hubiera querido trabajar.
Se me ocurrió el siguiente algoritmo para este problema, parece funcionar para todas las entradas. Además, si el valor de las acciones sigue bajando, el programa no emitirá para comprar estas acciones:
public class GetMaxProfit
{
double minValue = -1, maxValue = -1;
double maxDiff = 0;
public void getProfit(double [] inputArray){
int i=0, j=1;
double newDiff = 0;
while(j<inputArray.length){
newDiff = inputArray[j]-inputArray[i];
if(newDiff > 0){
if(newDiff > this.maxDiff){
this.minValue = inputArray[i];
this.maxValue = inputArray[j];
this.maxDiff = newDiff;
}
}
else{
i = j;
}
j++;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
GetMaxProfit obj = new GetMaxProfit();
obj.getProfit(new double[]{55.39, 19.23, 14.29, 11.59, 10.53, 9.45, 1.24});
if(obj.minValue != -1 && obj.maxValue != -1){
System.out.println("Buy Value for the input: "+obj.minValue);
System.out.println("Sell Value for the input: "+obj.maxValue);
System.out.println("Best profit for the input: "+obj.maxDiff);
}
else
System.out.println("Do Not Buy This STOCK!!);
}
}
¿Hay alguna trampa que puedas encontrar en esto? Es la complejidad del tiempo es O (N)
Solución en javascript
var stockArr = [13931, 9889, 987, 4, 89, 100];
function getBestTime(sortedArr) {
var min = 0;
var buyIndx = 0;
var saleIndx = 0;
var maxDiff = 0;
for (var i = 0; i < stockArr.length; i++) {
if (stockArr[i] < stockArr[min]) {
min = i;
}
var diff = stockArr[i] - stockArr[min];
if (diff > maxDiff) {
buy = min;
sale = i;
maxDiff = diff;
}
}
return {
buy:buy+1,
sale:sale+1,
diff:maxDiff
}
}
console.log(getBestTime(stockArr));
Solución en scala:
Ejemplo: [7, 2, 5, 6, 1, 3, 6, 4]
Mantenga un indicador del último precio mínimo de las acciones (lastStockPrice) y compárelo con el precio actual de las acciones. Cuando llega a un punto en el que el precio actual de las acciones <el último precio mínimo de las acciones, actualiza el último precio de inventario.
Mientras recorre la matriz, realice un seguimiento de la diferencia máxima (ganancia) entre el Precio actual y el Precio de la última compra, ya que la ganancia puede cambiar cuando actualice el Precio de la última venta.
El siguiente código de Scala funciona en tiempo O (n) y ocupa una cantidad constante de espacio.
object Solution {
def maxProfit(prices: Array[Int]): Int = {
var lastStockPrice = Int.MaxValue
var maxProfit = 0
for(currentPrice <- prices){
if(currentPrice < lastStockPrice){
lastStockPrice = currentPrice;
}else if(currentPrice - lastStockPrice > maxProfit){
maxProfit = currentPrice - lastStockPrice;
}
}
maxProfit
}
}
Tengo el 100% para el mismo, aquí tienes.
public int solution(int[] A) {
if (A == null || A.length<=1){
return 0;
}
int minValue = Math.min(A[0], A[1]);
int profit = A[1] - A[0];
for (int i = 2; i < A.length; i++) {
minValue = Math.min(minValue, A[i]);
profit = Math.max(A[i] - minValue,profit);
}
return profit > 0 ? profit : 0;
}
que tal esto
min = 100000000
max = 0
for elem in inp:
if elem < min:
min = elem
tempMax = elem-min
if tempMax > max:
max = tempMax
print(max)
public void profit(float stock[], int arlen ){
float buy = stock[0];
float sell = stock[arlen-1];
int bi = 0;
int si = arlen - 1;
for( int i = 0; i < arlen && bi < si ; i++){
if( stock[i] < buy && i < si){
buy = stock[i];
bi = i;
}
if(stock[arlen - i - 1] > sell && (arlen - i -1) > bi){
sell = stock[arlen - i - 1];
si = arlen - i - 1;
}
}
System.out.println(buy+" "+sell);
}
void getBestTime (int stocks[], int sz, int &buy, int &sell){
int min = 0;
int maxDiff = 0;
buy = sell = 0;
for (int i = 0; i < sz; i++)
{
if (stocks[i] < stocks[min])
{
min = i;
}
int diff = stocks[i] - stocks[min];
if (diff > maxDiff)
{
buy = min;
sell = i;
maxDiff = diff;
}
}}
Por si acaso prefieres esta respuesta. Lo encontré en otra web, pero aún así. fuente: http://leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html