Учитывая, что количество времени и отпускной цены находят лучшее время покупки и продажи, чтобы максимизировать прибыль

Question

Учитывая [(02:00, 7,5), (03:30, 7,9), (04:00, 8,0), (05 : 30, 6.8), (10:00, 9.01)] раз и продажная цена нам нужно найти лучшее время для покупки и продажи, чтобы максимизировать прибыль. // раз в порядке возрастания // Выходной сигнал: Покупайте в 05:30 и продавайте в 10:00 с прибылью в размере 2.21

Я написал логику, чтобы найти максимальную прибыль, но мне также нужно найти лучшая покупка и продажа время, поэтому я немного застряли там

double profit(double prices[]) 
    { 
    double maxprofit=0; 

    for(int i=0;i<price.length;i++) 
    { 
    double min= values[i]; 
    for(int j=i+1;j<price.length;j++) 
    { 
     if(price[j]<price[min]) 
     min=values[min]; 

    } 
    profit=values[i]-min; 
    if(maxprofit<profit) 
    maxprofit=profit; 
else 
continue; 
} 

Answer 1

там нет необходимости использовать вложенный цикл, существует линейный алгоритм времени, который может решить эту проблему.

Существует очень подробное объяснение алгоритма here.

Вот как можно исправить код:

public double maxProfit(double[] prices) { 

    if (prices.length <= 1) return 0; 

    double minPrice = prices[0]; 
    double maxSoFar = Integer.MIN_VALUE; 
    double profitSoFar = Integer.MIN_VALUE; 

    for (int i = 1; i < prices.length; i++){ 
     profitSoFar = prices[i] - minPrice; 
     minPrice = Math.min(minPrice, prices[i]); 
     maxSoFar = Math.max(profitSoFar, maxSoFar); 

    } 

    return Math.max(maxSoFar, 0); 
}