Lucro máximo de venda única

Suponha que recebamos uma matriz de n números inteiros representando os preços das ações em um único dia. Queremos encontrar um par (buyDay, sellDay) , com buyDay ≤ sellDay , de modo que, se comprássemos as ações na buyDay e as vendêss na sellDay , maximizaríamos nosso lucro.

Claramente, existe uma solução O (n ² ) para o algoritmo, testando todos os pares possíveis (buyDay, sellDay) e tirando o melhor proveito de todos eles. No entanto, existe um algoritmo melhor, talvez um que seja executado em O (n) tempo?

Eu amo esse problema. É uma pergunta clássica de entrevista e, dependendo de como você pensa sobre isso, acabará obtendo soluções cada vez melhores. Certamente é possível fazer isso em um tempo melhor que O (n ² ), e listei três maneiras diferentes pelas quais você pode pensar sobre o problema aqui. Espero que isso responda sua pergunta!

Primeiro, a solução de dividir e conquistar. Vamos ver se conseguimos resolver isso dividindo a entrada pela metade, resolvendo o problema em cada sub-matriz e combinando as duas. Acontece que podemos fazer isso de maneira eficiente! A intuição é a seguinte. Se tivermos um único dia, a melhor opção é comprar nesse dia e depois revendê-lo no mesmo dia sem fins lucrativos. Caso contrário, divida a matriz em duas metades. Se pensarmos sobre qual pode ser a resposta ideal, ela deve estar em um dos três lugares:

1. O par correto de compra / venda ocorre completamente na primeira metade.
2. O par correto de compra / venda ocorre completamente no segundo semestre.
3. O par correto de compra / venda ocorre nas duas metades - compramos no primeiro semestre e depois vendemos no segundo semestre.

Podemos obter os valores para (1) e (2) invocando recursivamente nosso algoritmo na primeira e na segunda metades. Para a opção (3), o caminho para obter o maior lucro seria comprar no ponto mais baixo do primeiro semestre e vender no ponto mais alto do segundo semestre. Podemos encontrar os valores mínimo e máximo nas duas metades, basta fazer uma varredura linear simples sobre a entrada e encontrar os dois valores. Isso nos fornece um algoritmo com a seguinte recorrência:

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)

Usando o Teorema Mestre para resolver a recorrência, descobrimos que isso é executado no tempo O (n lg n) e utilizará o espaço O (lg n) para as chamadas recursivas. Acabamos de vencer a solução ingênua de O (n ² )!

Mas espere! Podemos fazer muito melhor que isso. Observe que a única razão pela qual temos um termo O (n) em nossa recorrência é que tivemos que varrer toda a entrada tentando encontrar os valores mínimo e máximo em cada metade. Como já estamos explorando recursivamente cada metade, talvez possamos fazer melhor com a recursão também devolvendo os valores mínimo e máximo armazenados em cada metade! Em outras palavras, nossa recursão devolve três coisas:

1. Os tempos de compra e venda para maximizar o lucro.
2. O valor mínimo geral no intervalo.
3. O valor máximo geral no intervalo.

Esses dois últimos valores podem ser computados recursivamente usando uma recursão direta que podemos executar ao mesmo tempo que a recursão para calcular (1):

1. Os valores máximo e mínimo de um intervalo de elemento único são exatamente esse elemento.
2. Os valores max e min de um intervalo de vários elementos podem ser encontrados dividindo a entrada pela metade, localizando os valores max e min de cada metade e, em seguida, obtendo seus respectivos max e min.

Se usarmos essa abordagem, nossa relação de recorrência será agora

T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)

Usar o Teorema Mestre aqui nos fornece um tempo de execução de O (n) com O (lg n), o que é ainda melhor que a nossa solução original!

Mas espere um minuto - podemos fazer ainda melhor do que isso! Vamos pensar em resolver esse problema usando programação dinâmica. A idéia será pensar sobre o problema da seguinte maneira. Suponha que soubéssemos a resposta para o problema depois de examinar os primeiros k elementos. Poderíamos usar nosso conhecimento do (k + 1) st elemento, combinado com a nossa solução inicial, para resolver o problema dos primeiros (k + 1) elementos? Nesse caso, poderíamos obter um ótimo algoritmo resolvendo o problema do primeiro elemento, depois dos dois primeiros, depois dos três primeiros, etc. até calculá-lo para os primeiros n elementos.

Vamos pensar em como fazer isso. Se tivermos apenas um elemento, já sabemos que esse deve ser o melhor par de compra / venda. Agora, suponha que sabemos a melhor resposta para os primeiros k elementos e olhemos para o (k + 1) st elemento. Então, a única maneira de esse valor criar uma solução melhor do que a que possuíamos para os primeiros k elementos é se a diferença entre o menor dos primeiros elementos k e o novo elemento for maior que a maior diferença que computamos até agora. Portanto, suponha que, ao percorrermos os elementos, controlemos dois valores - o valor mínimo que vimos até agora e o lucro máximo que poderíamos obter com apenas os primeiros k elementos. Inicialmente, o valor mínimo que vimos até agora é o primeiro elemento e o lucro máximo é zero. Quando vemos um novo elemento, primeiro atualizamos nosso lucro ideal calculando quanto ganharíamos comprando pelo preço mais baixo visto até agora e vendendo pelo preço atual. Se isso for melhor do que o valor ideal que calculamos até agora, atualizamos a solução ideal para obter esse novo lucro. Em seguida, atualizamos o elemento mínimo visto até o momento como o mínimo do menor elemento atual e o novo elemento.

Como em cada etapa, fazemos apenas O (1) trabalho e visitamos cada um dos n elementos exatamente uma vez, isso leva O (n) tempo para ser concluído! Além disso, ele usa apenas armazenamento auxiliar O (1). Isso é tão bom quanto chegamos até agora!

Como exemplo, em suas entradas, veja como esse algoritmo pode ser executado. Os números entre cada um dos valores da matriz correspondem aos valores mantidos pelo algoritmo naquele momento. Na verdade, você não armazenaria tudo isso (seria necessário memória O (n)!), Mas é útil ver o algoritmo evoluir:

            5        10        4          6         7
min         5         5        4          4         4    
best      (5,5)     (5,10)   (5,10)     (5,10)    (5,10)

Resposta: (5, 10)

            5        10        4          6        12
min         5         5        4          4         4    
best      (5,5)     (5,10)   (5,10)     (5,10)    (4,12)

Resposta: (4, 12)

            1       2       3      4      5
min         1       1       1      1      1
best      (1,1)   (1,2)   (1,3)  (1,4)  (1,5)

Resposta: (1, 5)

Podemos fazer melhor agora? Infelizmente, não em um sentido assintótico. Se usarmos menos de O (n) tempo, não podemos olhar para todos os números em entradas grandes e, portanto, não podemos garantir que não perderemos a resposta ideal (poderíamos simplesmente "ocultá-la" nos elementos que não olhou). Além disso, não podemos usar menos que O (1) espaço. Pode haver algumas otimizações para os fatores constantes ocultos na notação big-O, mas, caso contrário, não podemos esperar encontrar opções radicalmente melhores.

No geral, isso significa que temos os seguintes algoritmos:

• Ingênuo: O (n ² ) tempo, O (1) espaço.
• Divida e conquiste: O (n lg n) tempo, O (lg n) espaço.
• Divisão e conquista otimizadas: O (n) tempo, O (lg n) espaço.
• Programação dinâmica: O (n) tempo, O (1) espaço.

Espero que isto ajude!

Edição : Se você estiver interessado, eu codifiquei uma versão Python desses quatro algoritmos para que você possa brincar com eles e julgar seu desempenho relativo. Aqui está o código:

# Four different algorithms for solving the maximum single-sell profit problem,
# each of which have different time and space complexity.  This is one of my
# all-time favorite algorithms questions, since there are so many different
# answers that you can arrive at by thinking about the problem in slightly
# different ways.
#
# The maximum single-sell profit problem is defined as follows.  You are given
# an array of stock prices representing the value of some stock over time.
# Assuming that you are allowed to buy the stock exactly once and sell the
# stock exactly once, what is the maximum profit you can make?  For example,
# given the prices
#
#                        2, 7, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5
#
# The maximum profit you can make is 8, by buying when the stock price is 1 and
# selling when the stock price is 9.  Note that while the greatest difference
# in the array is 9 (by subtracting 9 - 0), we cannot actually make a profit of
# 9 here because the stock price of 0 comes after the stock price of 9 (though
# if we wanted to lose a lot of money, buying high and selling low would be a
# great idea!)
#
# In the event that there's no profit to be made at all, we can always buy and
# sell on the same date.  For example, given these prices (which might
# represent a buggy-whip manufacturer:)
#
#                            9, 8, 7, 6, 5, 4, 3, 2, 1, 0
#
# The best profit we can make is 0 by buying and selling on the same day.
#
# Let's begin by writing the simplest and easiest algorithm we know of that
# can solve this problem - brute force.  We will just consider all O(n^2) pairs
# of values, and then pick the one with the highest net profit.  There are
# exactly n + (n - 1) + (n - 2) + ... + 1 = n(n + 1)/2 different pairs to pick
# from, so this algorithm will grow quadratically in the worst-case.  However,
# it uses only O(1) memory, which is a somewhat attractive feature.  Plus, if
# our first intuition for the problem gives a quadratic solution, we can be
# satisfied that if we don't come up with anything else, we can always have a
# polynomial-time solution.

def BruteForceSingleSellProfit(arr):
    # Store the best possible profit we can make; initially this is 0.
    bestProfit = 0;

    # Iterate across all pairs and find the best out of all of them.  As a
    # minor optimization, we don't consider any pair consisting of a single
    # element twice, since we already know that we get profit 0 from this.
    for i in range(0, len(arr)):
        for j in range (i + 1, len(arr)):
            bestProfit = max(bestProfit, arr[j] - arr[i])

    return bestProfit

# This solution is extremely inelegant, and it seems like there just *has* to
# be a better solution.  In fact, there are many better solutions, and we'll
# see three of them.
#
# The first insight comes if we try to solve this problem by using a divide-
# and-conquer strategy.  Let's consider what happens if we split the array into
# two (roughly equal) halves.  If we do so, then there are three possible
# options about where the best buy and sell times are:
#
# 1. We should buy and sell purely in the left half of the array.
# 2. We should buy and sell purely in the right half of the array.
# 3. We should buy in the left half of the array and sell in the right half of
#    the array.
#
# (Note that we don't need to consider selling in the left half of the array
# and buying in the right half of the array, since the buy time must always
# come before the sell time)
#
# If we want to solve this problem recursively, then we can get values for (1)
# and (2) by recursively invoking the algorithm on the left and right
# subarrays.  But what about (3)?  Well, if we want to maximize our profit, we
# should be buying at the lowest possible cost in the left half of the array
# and selling at the highest possible cost in the right half of the array.
# This gives a very elegant algorithm for solving this problem:
#
#    If the array has size 0 or size 1, the maximum profit is 0.
#    Otherwise:
#       Split the array in half.
#       Compute the maximum single-sell profit in the left array, call it L.
#       Compute the maximum single-sell profit in the right array, call it R.
#       Find the minimum of the first half of the array, call it Min
#       Find the maximum of the second half of the array, call it Max
#       Return the maximum of L, R, and Max - Min.
#
# Let's consider the time and space complexity of this algorithm.  Our base
# case takes O(1) time, and in our recursive step we make two recursive calls,
# one on each half of the array, and then does O(n) work to scan the array
# elements to find the minimum and maximum values.  This gives the recurrence
#
#    T(1)     = O(1)
#    T(n / 2) = 2T(n / 2) + O(n)
#
# Using the Master Theorem, this recurrence solves to O(n log n), which is
# asymptotically faster than our original approach!  However, we do pay a
# (slight) cost in memory usage.  Because we need to maintain space for all of
# the stack frames we use.  Since on each recursive call we cut the array size
# in half, the maximum number of recursive calls we can make is O(log n), so
# this algorithm uses O(n log n) time and O(log n) memory.

def DivideAndConquerSingleSellProfit(arr):
    # Base case: If the array has zero or one elements in it, the maximum
    # profit is 0.
    if len(arr) <= 1:
        return 0;

    # Cut the array into two roughly equal pieces.
    left  = arr[ : len(arr) / 2]
    right = arr[len(arr) / 2 : ]

    # Find the values for buying and selling purely in the left or purely in
    # the right.
    leftBest  = DivideAndConquerSingleSellProfit(left)
    rightBest = DivideAndConquerSingleSellProfit(right)

    # Compute the best profit for buying in the left and selling in the right.
    crossBest = max(right) - min(left)

    # Return the best of the three
    return max(leftBest, rightBest, crossBest)

# While the above algorithm for computing the maximum single-sell profit is
# better timewise than what we started with (O(n log n) versus O(n^2)), we can
# still improve the time performance.  In particular, recall our recurrence
# relation:
#
#    T(1) = O(1)
#    T(n) = 2T(n / 2) + O(n)
#
# Here, the O(n) term in the T(n) case comes from the work being done to find
# the maximum and minimum values in the right and left halves of the array,
# respectively.  If we could find these values faster than what we're doing
# right now, we could potentially decrease the function's runtime.
#
# The key observation here is that we can compute the minimum and maximum
# values of an array using a divide-and-conquer approach.  Specifically:
#
#    If the array has just one element, it is the minimum and maximum value.
#    Otherwise:
#       Split the array in half.
#       Find the minimum and maximum values from the left and right halves.
#       Return the minimum and maximum of these two values.
#
# Notice that our base case does only O(1) work, and our recursive case manages
# to do only O(1) work in addition to the recursive calls.  This gives us the
# recurrence relation
#
#    T(1) = O(1)
#    T(n) = 2T(n / 2) + O(1)
#
# Using the Master Theorem, this solves to O(n).
#
# How can we make use of this result?  Well, in our current divide-and-conquer
# solution, we split the array in half anyway to find the maximum profit we
# could make in the left and right subarrays.  Could we have those recursive
# calls also hand back the maximum and minimum values of the respective arrays?
# If so, we could rewrite our solution as follows:
#
#    If the array has size 1, the maximum profit is zero and the maximum and
#       minimum values are the single array element.
#    Otherwise:
#       Split the array in half.
#       Compute the maximum single-sell profit in the left array, call it L.
#       Compute the maximum single-sell profit in the right array, call it R.
#       Let Min be the minimum value in the left array, which we got from our
#           first recursive call.
#       Let Max be the maximum value in the right array, which we got from our
#           second recursive call.
#       Return the maximum of L, R, and Max - Min for the maximum single-sell
#           profit, and the appropriate maximum and minimum values found from
#           the recursive calls.
#
# The correctness proof for this algorithm works just as it did before, but now
# we never actually do a scan of the array at each step.  In fact, we do only
# O(1) work at each level.  This gives a new recurrence
#
#     T(1) = O(1)
#     T(n) = 2T(n / 2) + O(1)
#
# Which solves to O(n).  We're now using O(n) time and O(log n) memory, which
# is asymptotically faster than before!
#
# The code for this is given below:

def OptimizedDivideAndConquerSingleSellProfit(arr):
    # If the array is empty, the maximum profit is zero.
    if len(arr) == 0:
        return 0

    # This recursive helper function implements the above recurrence.  It
    # returns a triple of (max profit, min array value, max array value).  For
    # efficiency reasons, we always reuse the array and specify the bounds as
    # [lhs, rhs]
    def Recursion(arr, lhs, rhs):
        # If the array has just one element, we return that the profit is zero
        # but the minimum and maximum values are just that array value.
        if lhs == rhs:
            return (0, arr[lhs], arr[rhs])

        # Recursively compute the values for the first and latter half of the
        # array.  To do this, we need to split the array in half.  The line
        # below accomplishes this in a way that, if ported to other languages,
        # cannot result in an integer overflow.
        mid = lhs + (rhs - lhs) / 2

        # Perform the recursion.
        ( leftProfit,  leftMin,  leftMax) = Recursion(arr, lhs, mid)
        (rightProfit, rightMin, rightMax) = Recursion(arr, mid + 1, rhs)

        # Our result is the maximum possible profit, the minimum of the two
        # minima we've found (since the minimum of these two values gives the
        # minimum of the overall array), and the maximum of the two maxima.
        maxProfit = max(leftProfit, rightProfit, rightMax - leftMin)
        return (maxProfit, min(leftMin, rightMin), max(leftMax, rightMax))

    # Using our recursive helper function, compute the resulting value.
    profit, _, _ = Recursion(arr, 0, len(arr) - 1)
    return profit

# At this point we've traded our O(n^2)-time, O(1)-space solution for an O(n)-
# time, O(log n) space solution.  But can we do better than this?
#
# To find a better algorithm, we'll need to switch our line of reasoning.
# Rather than using divide-and-conquer, let's see what happens if we use
# dynamic programming.  In particular, let's think about the following problem.
# If we knew the maximum single-sell profit that we could get in just the first
# k array elements, could we use this information to determine what the
# maximum single-sell profit would be in the first k + 1 array elements?  If we
# could do this, we could use the following algorithm:
#
#   Find the maximum single-sell profit to be made in the first 1 elements.
#   For i = 2 to n:
#      Compute the maximum single-sell profit using the first i elements.
#
# How might we do this?  One intuition is as follows.  Suppose that we know the
# maximum single-sell profit of the first k elements.  If we look at k + 1
# elements, then either the maximum profit we could make by buying and selling
# within the first k elements (in which case nothing changes), or we're
# supposed to sell at the (k + 1)st price.  If we wanted to sell at this price
# for a maximum profit, then we would want to do so by buying at the lowest of
# the first k + 1 prices, then selling at the (k + 1)st price.
#
# To accomplish this, suppose that we keep track of the minimum value in the
# first k elements, along with the maximum profit we could make in the first
# k elements.  Upon seeing the (k + 1)st element, we update what the current
# minimum value is, then update what the maximum profit we can make is by
# seeing whether the difference between the (k + 1)st element and the new
# minimum value is.  Note that it doesn't matter what order we do this in; if
# the (k + 1)st element is the smallest element so far, there's no possible way
# that we could increase our profit by selling at that point.
#
# To finish up this algorithm, we should note that given just the first price,
# the maximum possible profit is 0.
#
# This gives the following simple and elegant algorithm for the maximum single-
# sell profit problem:
#
#   Let profit = 0.
#   Let min = arr[0]
#   For k = 1 to length(arr):
#       If arr[k] < min, set min = arr[k]
#       If profit < arr[k] - min, set profit = arr[k] - min
#
# This is short, sweet, and uses only O(n) time and O(1) memory.  The beauty of
# this solution is that we are quite naturally led there by thinking about how
# to update our answer to the problem in response to seeing some new element.
# In fact, we could consider implementing this algorithm as a streaming
# algorithm, where at each point in time we maintain the maximum possible
# profit and then update our answer every time new data becomes available.
#
# The final version of this algorithm is shown here:

def DynamicProgrammingSingleSellProfit(arr):
    # If the array is empty, we cannot make a profit.
    if len(arr) == 0:
        return 0

    # Otherwise, keep track of the best possible profit and the lowest value
    # seen so far.
    profit = 0
    cheapest = arr[0]

    # Iterate across the array, updating our answer as we go according to the
    # above pseudocode.
    for i in range(1, len(arr)):
        # Update the minimum value to be the lower of the existing minimum and
        # the new minimum.
        cheapest = min(cheapest, arr[i])

        # Update the maximum profit to be the larger of the old profit and the
        # profit made by buying at the lowest value and selling at the current
        # price.
        profit = max(profit, arr[i] - cheapest)

    return profit

# To summarize our algorithms, we have seen
#
# Naive:                        O(n ^ 2)   time, O(1)     space
# Divide-and-conquer:           O(n log n) time, O(log n) space
# Optimized divide-and-conquer: O(n)       time, O(log n) space
# Dynamic programming:          O(n)       time, O(1)     space

Esse é o problema de subsequência da soma máxima com um pouco de indireção. O problema da subsequência da soma máxima recebe uma lista de números inteiros que podem ser positivos ou negativos; encontre a maior soma de um subconjunto contíguo dessa lista.

Você pode converter esse problema trivialmente para esse problema obtendo lucros ou perdas entre dias consecutivos. Então você transformaria uma lista de preços das ações, por exemplo, [5, 6, 7, 4, 2]em uma lista de ganhos / perdas, por exemplo [1, 1, -3, -2],. O problema da soma de subsequência é muito fácil de resolver: encontre a subsequência com a maior soma de elementos em uma matriz

Não sei ao certo por que isso é considerado uma questão de programação dinâmica. Eu já vi essa pergunta em livros didáticos e guias de algoritmos usando O (n log n) runtime e O (log n) como espaço (por exemplo, elementos de entrevistas de programação). Parece um problema muito mais simples do que as pessoas estão fazendo parecer.

Isso funciona acompanhando o lucro máximo, o preço mínimo de compra e, consequentemente, o preço ótimo de compra / venda. À medida que percorre cada elemento da matriz, ele verifica se o elemento fornecido é menor que o preço mínimo de compra. Se for, o índice mínimo de preço de compra ( min) será atualizado para ser o índice desse elemento. Além disso, para cada elemento, o becomeABillionairealgoritmo verifica se arr[i] - arr[min](a diferença entre o elemento atual e o preço mínimo de compra) é maior que o lucro atual. Se for, o lucro é atualizado para essa diferença e a compra é definida como arr[min]e a venda é definida como arr[i].

É executado em um único passe.

static void becomeABillionaire(int arr[]) {
    int i = 0, buy = 0, sell = 0, min = 0, profit = 0;

    for (i = 0; i < arr.length; i++) {
        if (arr[i] < arr[min])
            min = i;
        else if (arr[i] - arr[min] > profit) {
            buy = min; 
            sell = i;
            profit = arr[i] - arr[min];
        }

    }

    System.out.println("We will buy at : " + arr[buy] + " sell at " + arr[sell] + 
            " and become billionaires worth " + profit );

}

Co-autor: https://stackoverflow.com/users/599402/ephraim

O problema é idêntico à subseqüência máxima que
eu resolvi usando a programação dinâmica. Acompanhe o atual e o anterior (data de lucro, data de compra e venda) Se a corrente for maior que a anterior, substitua a anterior por atual.

    int prices[] = { 38, 37, 35, 31, 20, 24, 35, 21, 24, 21, 23, 20, 23, 25, 27 };

    int buyDate = 0, tempbuyDate = 0;
    int sellDate = 0, tempsellDate = 0; 

    int profit = 0, tempProfit =0;
    int i ,x = prices.length;
    int previousDayPrice = prices[0], currentDayprice=0;

    for(i=1 ; i<x; i++ ) {

        currentDayprice = prices[i];

        if(currentDayprice > previousDayPrice ) {  // price went up

            tempProfit = tempProfit + currentDayprice - previousDayPrice;
            tempsellDate = i;
        }
        else { // price went down 

            if(tempProfit>profit) { // check if the current Profit is higher than previous profit....

                profit = tempProfit;
                sellDate = tempsellDate;
                buyDate = tempbuyDate;
            } 
                                     // re-intialized buy&sell date, profit....
                tempsellDate = i;
                tempbuyDate = i;
                tempProfit =0;
        }
        previousDayPrice = currentDayprice;
    }

    // if the profit is highest till the last date....
    if(tempProfit>profit) {
        System.out.println("buydate " + tempbuyDate + " selldate " + tempsellDate + " profit " + tempProfit );
    }
    else {
        System.out.println("buydate " + buyDate + " selldate " + sellDate + " profit " + profit );
    }   

aqui está a minha solução Java:

public static void main(String[] args) {
    int A[] = {5,10,4,6,12};

    int min = A[0]; // Lets assume first element is minimum
    int maxProfit = 0; // 0 profit, if we buy & sell on same day.
    int profit = 0;
    int minIndex = 0; // Index of buy date
    int maxIndex = 0; // Index of sell date

    //Run the loop from next element
    for (int i = 1; i < A.length; i++) {
        //Keep track of minimum buy price & index
        if (A[i] < min) {
            min = A[i];
            minIndex = i;
        }
        profit = A[i] - min;
        //If new profit is more than previous profit, keep it and update the max index
        if (profit > maxProfit) {
            maxProfit = profit;
            maxIndex = i;
        }
    }
    System.out.println("maxProfit is "+maxProfit);
    System.out.println("minIndex is "+minIndex);
    System.out.println("maxIndex is "+maxIndex);     
}

Eu vim com uma solução simples - o código é mais auto-explicativo. É uma daquelas questões de programação dinâmica.

O código não cuida da verificação de erros e dos casos extremos. É apenas uma amostra para dar a idéia da lógica básica para resolver o problema.

namespace MaxProfitForSharePrice
{
    class MaxProfitForSharePrice
    {
        private static int findMax(int a, int b)
        {
            return a > b ? a : b;
        }

        private static void GetMaxProfit(int[] sharePrices)
        {
            int minSharePrice = sharePrices[0], maxSharePrice = 0, MaxProft = 0;
            int shareBuyValue = sharePrices[0], shareSellValue = sharePrices[0];

            for (int i = 0; i < sharePrices.Length; i++)
            {
                if (sharePrices[i] < minSharePrice )
                {
                    minSharePrice = sharePrices[i];
                    // if we update the min value of share, we need to reset the Max value as 
                    // we can only do this transaction in-sequence. We need to buy first and then only we can sell.
                    maxSharePrice = 0; 
                }
                else 
                {
                    maxSharePrice = sharePrices[i];
                }

                // We are checking if max and min share value of stock are going to
                // give us better profit compare to the previously stored one, then store those share values.
                if (MaxProft < (maxSharePrice - minSharePrice))
                {
                    shareBuyValue = minSharePrice;
                    shareSellValue = maxSharePrice;
                }

                MaxProft = findMax(MaxProft, maxSharePrice - minSharePrice);
            }

            Console.WriteLine("Buy stock at ${0} and sell at ${1}, maximum profit can be earned ${2}.", shareBuyValue, shareSellValue, MaxProft);
        }

        static void Main(string[] args)
        {
           int[] sampleArray = new int[] { 1, 3, 4, 1, 1, 2, 11 };
           GetMaxProfit(sampleArray);
            Console.ReadLine();
        }
    }
}

public static double maxProfit(double [] stockPrices)
    {
        double initIndex = 0, finalIndex = 0;

        double tempProfit = list[1] - list[0];
        double maxSum = tempProfit;
        double maxEndPoint = tempProfit;


        for(int i = 1 ;i<list.length;i++)
        {
            tempProfit = list[ i ] - list[i - 1];;

            if(maxEndPoint < 0)
            {
                maxEndPoint = tempProfit;
                initIndex = i;
            }
            else
            {
                maxEndPoint += tempProfit;
            }

            if(maxSum <= maxEndPoint)
            {
                maxSum = maxEndPoint ;
                finalIndex = i;
            }
        }
        System.out.println(initIndex + " " + finalIndex);
        return maxSum;

    }

Aqui está a minha solução. modifica o algoritmo máximo de sub-sequência. Resolve o problema em O (n). Eu acho que não pode ser feito mais rápido.

Esse é um problema interessante, porque parece difícil, mas um pensamento cuidadoso produz uma solução elegante e simplificada.

Como foi observado, ele pode ser resolvido com força bruta no tempo O (N ^ 2). Para cada entrada na matriz (ou lista), repita todas as entradas anteriores para obter o mínimo ou o máximo, dependendo se o problema é encontrar o maior ganho ou perda.

Veja como pensar em uma solução em O (N): cada entrada representa um novo máximo possível (ou min). Então, tudo o que precisamos fazer é salvar o mínimo anterior (ou máximo) e comparar o diff com o atual e o mínimo anterior (ou máximo). Mole-mole.

Aqui está o código, em Java, como um teste JUnit:

import org.junit.Test;

public class MaxDiffOverSeriesProblem {

    @Test
    public void test1() {
        int[] testArr = new int[]{100, 80, 70, 65, 95, 120, 150, 75, 95, 100, 110, 120, 90, 80, 85, 90};

        System.out.println("maxLoss: " + calculateMaxLossOverSeries(testArr) + ", maxGain: " + calculateMaxGainOverSeries(testArr));
    }

    private int calculateMaxLossOverSeries(int[] arr) {
        int maxLoss = 0;

        int idxMax = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[idxMax]) {
                idxMax = i;
            }

            if (arr[idxMax] - arr[i] > maxLoss) {
                maxLoss = arr[idxMax] - arr[i];
            }           
        }

        return maxLoss;
    }

    private int calculateMaxGainOverSeries(int[] arr) {
        int maxGain = 0;

        int idxMin = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < arr[idxMin]) {
                idxMin = i;
            }

            if (arr[i] - arr[idxMin] > maxGain) {
                maxGain = arr[i] - arr[idxMin];
            }           
        }

        return maxGain;
    }

}

No caso de calcular a maior perda, acompanhamos o máximo na lista (preço de compra) até a entrada atual. Em seguida, calculamos a diferença entre a entrada máxima e a atual. Se max - current> maxLoss, mantemos essa diferença como o novo maxLoss. Como o índice max é garantido inferior ao índice atual, garantimos que a data de compra é menor que a data de venda.

No caso de calcular o maior ganho, tudo é revertido. Nós acompanhamos os minutos na lista até a entrada atual. Calculamos a diferença entre a entrada mínima e a entrada atual (revertendo a ordem na subtração). Se current - min> maxGain, mantemos essa diferença como o novo maxGain. Novamente, o índice de 'compra' (min) vem antes do índice de corrente ('venda').

Precisamos apenas acompanhar o maxGain (ou maxLoss) e o índice de min ou max, mas não ambos, e não precisamos comparar índices para validar que 'comprar' é menor que 'vender', pois pegue isso naturalmente.

Lucro máximo de venda única, solução O (n)

function stocks_n(price_list){
    var maxDif=0, min=price_list[0]

    for (var i in price_list){
        p = price_list[i];
        if (p<min)
            min=p
        else if (p-min>maxDif)
                maxDif=p-min;
   }

    return maxDif
}

Aqui está um projeto que faz testes de complexidade de tempo em abordagens o (N) vs o (n ^ 2) em um conjunto de dados aleatórios em 100k ints. O (n ^ 2) leva 2 segundos, enquanto O (n) leva 0,01s

https://github.com/gulakov/complexity.js

function stocks_n2(ps){
    for (maxDif=0,i=_i=0;p=ps[i++];i=_i++)
        for (;p2=ps[i++];)
            if (p2-p>maxDif)
                maxDif=p2-p
    return maxDif
}

Essa é a abordagem mais lenta, o (n ^ 2), que faz um loop pelo resto dos dias de cada dia, em loop duplo.

A resposta mais votada não permite casos em que o lucro máximo é negativo e deve ser modificado para permitir tais casos. Pode-se fazer isso limitando o intervalo do loop para (len (a) - 1) e alterando a maneira como o lucro é determinado deslocando o índice por um.

def singSellProfit(a):
profit = -max(a)
low = a[0]

for i in range(len(a) - 1):
    low = min(low, a[i])
    profit = max(profit, a[i + 1] - low)
return profit

Compare esta versão da função com a anterior para a matriz:

s = [19,11,10,8,5,2]

singSellProfit(s)
-1

DynamicProgrammingSingleSellProfit(s)
0

static void findmaxprofit(int[] stockvalues){
    int buy=0,sell=0,buyingpoint=0,sellingpoint=0,profit=0,currentprofit=0;
    int finalbuy=0,finalsell=0;
    if(stockvalues.length!=0){
        buy=stockvalues[0];
    }           
    for(int i=1;i<stockvalues.length;i++){  
        if(stockvalues[i]<buy&&i!=stockvalues.length-1){                
            buy=stockvalues[i];
            buyingpoint=i;
        }               
        else if(stockvalues[i]>buy){                
            sell=stockvalues[i];
            sellingpoint=i;
        }
        currentprofit=sell-buy;         
        if(profit<currentprofit&&sellingpoint>buyingpoint){             
            finalbuy=buy;
            finalsell=sell;
            profit=currentprofit;
        }

    }
    if(profit>0)
    System.out.println("Buy shares at "+finalbuy+" INR and Sell Shares "+finalsell+" INR and Profit of "+profit+" INR");
    else
        System.out.println("Don't do Share transacations today");
}

Uma possibilidade de determinar o lucro máximo pode ser manter o controle dos elementos mínimo esquerdo e máximo direito do array em cada índice do array. Quando você estiver percorrendo os preços das ações, em qualquer dia, você saberá o preço mais baixo até aquele dia e também saberá o preço máximo após (e incluindo) naquele dia.

Por exemplo, vamos definir a min_arre max_arr, com a matriz fornecida arr. O índice iem min_arrseria o elemento mínimo arrpara todos os índices <= i(à esquerda de e incluindo i). O índice iem max_arrseria o elemento máximo arrpara todos os índices >= i(direito de e incluindo i). Então, você pode encontrar a diferença máxima entre os elementos correspondentes em max_arre `min_arr ':

def max_profit(arr)
   min_arr = []
   min_el = arr.first
   arr.each do |el|
       if el < min_el
           min_el = el
           min_arr << min_el
       else
           min_arr << min_el
       end
   end

   max_arr = []
   max_el = arr.last
   arr.reverse.each do |el|
       if el > max_el
           max_el = el
           max_arr.unshift(max_el)
       else
           max_arr.unshift(max_el)
       end

   end

   max_difference = max_arr.first - min_arr.first
   1.upto(arr.length-1) do |i|
        max_difference = max_arr[i] - min_arr[i] if max_difference < max_arr[i] - min_arr[i]  
   end

   return max_difference 
end

Isso deve ser executado em O (n) tempo, mas acredito que consome muito espaço.

Essa é a diferença máxima entre dois elementos na matriz e esta é a minha solução:

O (N) complexidade do tempo O (1) complexidade do espaço

    int[] arr   =   {5, 4, 6 ,7 ,6 ,3 ,2, 5};

    int start   =   0;
    int end     =   0;
    int max     =   0;
    for(int i=1; i<arr.length; i++){
        int currMax =   arr[i] - arr[i-1];
        if(currMax>0){
            if((arr[i] -arr[start])>=currMax && ((arr[i] -arr[start])>=(arr[end] -arr[start]))){

                 end    =   i;
            }
            else if(currMax>(arr[i] -arr[start]) && currMax >(arr[end] - arr[start])){
                start   =   i-1;
                end =   i;
            }
        }
    }
    max =   arr[end] - arr[start];
    System.out.println("max: "+max+" start: "+start+" end: "+end);

Depois de falhar isso em um exame de codificação ao vivo para uma posição de engenheiro de soluções da FB, tive que resolvê-lo em uma atmosfera calma e fria, então aqui estão meus 2 centavos:

var max_profit = 0;
var stockPrices = [23,40,21,67,1,50,22,38,2,62];

var currentBestBuy = 0; 
var currentBestSell = 0;
var min = 0;

for(var i = 0;i < (stockPrices.length - 1) ; i++){
    if(( stockPrices[i + 1] - stockPrices[currentBestBuy] > max_profit) ){
        max_profit = stockPrices[i + 1] - stockPrices[currentBestBuy];
        currentBestSell = i + 1;  
    }
    if(stockPrices[i] < stockPrices[currentBestBuy]){
            min = i;
        }
    if( max_profit < stockPrices[i + 1] - stockPrices[min] ){
        max_profit = stockPrices[i + 1] - stockPrices[min];
        currentBestSell = i + 1;
        currentBestBuy = min;
    }
}

console.log(currentBestBuy);
console.log(currentBestSell);
console.log(max_profit);

A única resposta que realmente responde à pergunta é a de @akash_magoon (e de uma maneira tão simples!), Mas ela não retorna o objeto exato especificado na pergunta. Refatorei um pouco e tenho minha resposta em PHP retornando exatamente o que é solicitado:

function maximizeProfit(array $dailyPrices)
{
    $buyDay = $sellDay = $cheaperDay = $profit = 0;

    for ($today = 0; $today < count($dailyPrices); $today++) {
        if ($dailyPrices[$today] < $dailyPrices[$cheaperDay]) {
            $cheaperDay = $today;
        } elseif ($dailyPrices[$today] - $dailyPrices[$cheaperDay] > $profit) {
            $buyDay  = $cheaperDay;
            $sellDay = $today;
            $profit   = $dailyPrices[$today] - $dailyPrices[$cheaperDay];
        }
    }
    return [$buyDay, $sellDay];
}

Uma solução elegante:

+ (int)maxProfit:(NSArray *)prices {
    int maxProfit = 0;

    int bestBuy = 0;
    int bestSell = 0;
    int currentBestBuy = 0;

    for (int i= 1; i < prices.count; i++) {
        int todayPrice = [prices[i] intValue];
        int bestBuyPrice = [prices[currentBestBuy] intValue];
        if (todayPrice < bestBuyPrice) {
            currentBestBuy = i;
            bestBuyPrice = todayPrice;
        }

        if (maxProfit < (todayPrice - bestBuyPrice)) {
            bestSell = i;
            bestBuy = currentBestBuy;
            maxProfit = (todayPrice - bestBuyPrice);
        }
    }

    NSLog(@"Buy Day : %d", bestBuy);
    NSLog(@"Sell Day : %d", bestSell);

    return maxProfit;
}

def get_max_profit(stock):
    p=stock[0]
    max_profit=0
    maxp=p
    minp=p
    for i in range(1,len(stock)):
        p=min(p,stock[i])
        profit=stock[i]-p
        if profit>max_profit:
            maxp=stock[i]
            minp=p
            max_profit=profit
    return minp,maxp,max_profit



stock_prices = [310,315,275,295,260,270,290,230,255,250]
print(get_max_profit(stock_prices))

Este programa em python3 pode retornar o preço de compra e o preço de venda que maximizarão o lucro, calculado com a complexidade de tempo de O (n) e a complexidade de espaço de O (1) .

Aqui está a minha solução

public static int maxProfit(List<Integer> in) {
    int min = in.get(0), max = 0;
    for(int i=0; i<in.size()-1;i++){

        min=Math.min(min, in.get(i));

        max = Math.max(in.get(i) - min, max);
     }

     return max;
 }
}

Para todas as respostas que acompanham os elementos mínimo e máximo, essa solução é realmente uma solução O (n ^ 2). Isso ocorre porque, no final, deve-se verificar se o máximo ocorreu após o mínimo ou não. Caso contrário, são necessárias mais iterações até que essa condição seja atendida, e isso deixa o pior caso de O (n ^ 2). E se você quiser pular as iterações extras, será necessário muito mais espaço. De qualquer forma, um não-não, em comparação com a solução de programação dinâmica