Bénéfice maximal d'une seule vente

Supposons qu'on nous donne un tableau de n entiers représentant les cours des actions sur une seule journée. Nous voulons trouver une paire (buyDay, sellDay) , avec buyDay ≤ sellDay , de telle sorte que si nous achetions l'action le buyDay et la vendions le sellDay , nous maximiserions notre profit.

Il existe clairement une solution O (n ² ) à l'algorithme en essayant toutes les paires possibles (buyDay, sellDay) et en tirant le meilleur de toutes. Cependant, y a-t-il un meilleur algorithme, peut-être un qui s'exécute en temps O (n) ?

J'adore ce problème. C'est une question d'entrevue classique et selon la façon dont vous y pensez, vous obtiendrez de meilleures solutions. Il est certainement possible de le faire dans un temps meilleur que O (n ² ), et j'ai énuméré trois façons différentes de penser au problème ici. J'espère que cela répond à votre question!

Premièrement, la solution diviser pour vaincre. Voyons si nous pouvons résoudre cela en divisant l'entrée en deux, en résolvant le problème dans chaque sous-tableau, puis en combinant les deux ensemble. Il s'avère que nous pouvons réellement le faire et que nous pouvons le faire efficacement! L'intuition est la suivante. Si nous n'avons qu'un seul jour, la meilleure option est d'acheter ce jour-là et de le revendre le même jour sans profit. Sinon, divisez le tableau en deux moitiés. Si nous réfléchissons à ce que pourrait être la réponse optimale, elle doit être dans l'un des trois endroits suivants:

1. La bonne paire d'achat / vente se produit complètement dans la première moitié.
2. La bonne paire d'achat / vente se produit complètement dans la seconde moitié.
3. La bonne paire achat / vente se produit sur les deux moitiés - nous achetons au premier semestre, puis vendons au second semestre.

Nous pouvons obtenir les valeurs pour (1) et (2) en invoquant récursivement notre algorithme sur les première et deuxième moitiés. Pour l'option (3), le moyen de réaliser le profit le plus élevé serait d'acheter au point le plus bas du premier semestre et de vendre au point le plus élevé au second semestre. Nous pouvons trouver les valeurs minimum et maximum dans les deux moitiés en effectuant simplement un simple balayage linéaire sur l'entrée et en trouvant les deux valeurs. Cela nous donne alors un algorithme avec la récurrence suivante:

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

En utilisant le théorème maître pour résoudre la récurrence, nous trouvons que cela s'exécute en temps O (n lg n) et utilisera l'espace O (lg n) pour les appels récursifs. Nous venons de battre la solution naïve O (n ² )!

Mais attendez! Nous pouvons faire beaucoup mieux que cela. Notez que la seule raison pour laquelle nous avons un terme O (n) dans notre récurrence est que nous avons dû analyser toute l'entrée en essayant de trouver les valeurs minimum et maximum dans chaque moitié. Puisque nous explorons déjà chaque moitié de manière récursive, nous pouvons peut-être faire mieux en faisant en sorte que la récursion rende également les valeurs minimum et maximum stockées dans chaque moitié! En d'autres termes, notre récursivité rend trois choses:

1. Les délais d'achat et de vente pour maximiser le profit.
2. La valeur minimale globale de la plage.
3. La valeur maximale globale de la plage.

Ces deux dernières valeurs peuvent être calculées de manière récursive en utilisant une récursivité simple que nous pouvons exécuter en même temps que la récursivité à calculer (1):

1. Les valeurs max et min d'une plage à un seul élément ne sont que cet élément.
2. Les valeurs max et min d'une plage de plusieurs éléments peuvent être trouvées en divisant l'entrée en deux, en trouvant les valeurs max et min de chaque moitié, puis en prenant leurs valeurs max et min respectives.

Si nous utilisons cette approche, notre relation de récurrence est maintenant

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

L'utilisation du théorème maître nous donne ici un temps d'exécution de O (n) avec un espace O (lg n), ce qui est encore mieux que notre solution originale!

Mais attendez une minute - nous pouvons faire encore mieux que cela! Pensons à résoudre ce problème en utilisant la programmation dynamique. L'idée sera de réfléchir au problème comme suit. Supposons que nous connaissions la réponse au problème après avoir examiné les k premiers éléments. Pourrions-nous utiliser notre connaissance du (k + 1) premier élément, combinée à notre solution initiale, pour résoudre le problème des premiers (k + 1) éléments? Si c'est le cas, nous pourrions obtenir un excellent algorithme en résolvant le problème pour le premier élément, puis les deux premiers, puis les trois premiers, etc. jusqu'à ce que nous l'ayons calculé pour les n premiers éléments.

Réfléchissons à la façon de procéder. Si nous n'avons qu'un seul élément, nous savons déjà qu'il doit s'agir de la meilleure paire achat / vente. Supposons maintenant que nous connaissions la meilleure réponse pour les k premiers éléments et que nous regardions le (k + 1) élément. Ensuite, la seule façon pour cette valeur de créer une solution meilleure que ce que nous avions pour les k premiers éléments est de savoir si la différence entre le plus petit des k premiers éléments et ce nouvel élément est plus grande que la plus grande différence que nous avons calculée jusqu'à présent. Supposons donc qu'en parcourant les éléments, nous gardions une trace de deux valeurs - la valeur minimale que nous avons vue jusqu'à présent et le profit maximal que nous pourrions faire avec les k premiers éléments seulement. Au départ, la valeur minimale que nous avons vue jusqu'à présent est le premier élément et le profit maximal est nul. Quand nous voyons un nouvel élément, Nous mettons d'abord à jour notre profit optimal en calculant ce que nous gagnerions en achetant au prix le plus bas vu jusqu'à présent et en vendant au prix actuel. Si c'est mieux que la valeur optimale que nous avons calculée jusqu'à présent, nous mettons à jour la solution optimale pour être ce nouveau profit. Ensuite, nous mettons à jour l'élément minimum vu jusqu'à présent comme étant le minimum du plus petit élément actuel et du nouvel élément.

Étant donné qu'à chaque étape, nous ne faisons qu'un travail O (1) et que nous visitons chacun des n éléments exactement une fois, cela prend du temps O (n)! De plus, il n'utilise que la mémoire auxiliaire O (1). C'est aussi bon que nous en sommes jusqu'ici!

À titre d'exemple, sur vos entrées, voici comment cet algorithme pourrait fonctionner. Les nombres entre chacune des valeurs du tableau correspondent aux valeurs détenues par l'algorithme à ce point. Vous ne stockeriez pas vraiment tout cela (cela prendrait de la mémoire O (n)!), Mais il est utile de voir l'algorithme évoluer:

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

Réponse: (5, 10)

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

Réponse: (4, 12)

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

Réponse: (1, 5)

Pouvons-nous faire mieux maintenant? Malheureusement, pas dans un sens asymptotique. Si nous utilisons moins de temps O (n), nous ne pouvons pas regarder tous les nombres sur de grandes entrées et ne pouvons donc pas garantir que nous ne manquerons pas la réponse optimale (nous pourrions simplement la «cacher» dans les éléments que nous n'a pas regardé). De plus, nous ne pouvons pas utiliser moins que l'espace O (1). Il peut y avoir des optimisations des facteurs constants cachés dans la notation big-O, mais sinon, nous ne pouvons pas nous attendre à trouver des options radicalement meilleures.

Globalement, cela signifie que nous avons les algorithmes suivants:

• Naïf: temps O (n ² ), espace O (1).
• Diviser-et-Conquérir: O (n lg n) temps, O (lg n) espace.
• Optimisé Divide-and-Conquer: temps O (n), espace O (lg n).
• Programmation dynamique: temps O (n), espace O (1).

J'espère que cela t'aides!

EDIT : Si vous êtes intéressé, j'ai codé une version Python de ces quatre algorithmes afin que vous puissiez jouer avec eux et juger de leurs performances relatives. Voici le code:

# 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

C'est le problème de sous-séquence de somme maximale avec un peu d'indirection. Le problème de sous-séquence de somme maximale reçoit une liste d'entiers qui peuvent être positifs ou négatifs, trouvez la plus grande somme d'un sous-ensemble contigu de cette liste.

Vous pouvez facilement convertir ce problème en ce problème en prenant le profit ou la perte entre des jours consécutifs. Ainsi, vous transformeriez une liste de cours boursiers, par exemple [5, 6, 7, 4, 2]en une liste de gains / pertes, par exemple [1, 1, -3, -2]. Le problème de la somme des sous-séquences est alors assez facile à résoudre: Trouvez la sous-séquence avec la plus grande somme d'éléments dans un tableau

Je ne sais pas vraiment pourquoi cela est considéré comme une question de programmation dynamique. J'ai vu cette question dans les manuels et les guides d'algorithmes utilisant le runtime O (n log n) et O (log n) pour l'espace (par exemple, Elements of Programming Interviews). Cela semble être un problème beaucoup plus simple que ce que les gens prétendent.

Cela fonctionne en gardant une trace du profit maximum, du prix d'achat minimum et, par conséquent, du prix d'achat / de vente optimal. En parcourant chaque élément du tableau, il vérifie si l'élément donné est plus petit que le prix d'achat minimum. Si tel est le cas, l'indice de prix d'achat minimum, ( min), est mis à jour pour être l'indice de cet élément. De plus, pour chaque élément, l' becomeABillionairealgorithme vérifie si arr[i] - arr[min](la différence entre l'élément actuel et le prix d'achat minimum) est supérieure au profit actuel. Si tel est le cas, le profit est mis à jour en fonction de cette différence et acheter est défini sur arr[min]et vendre est défini sur arr[i].

Fonctionne en un seul passage.

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-auteur: https://stackoverflow.com/users/599402/ephraim

Le problème est identique à la sous-séquence maximale que
je l'ai résolu en utilisant la programmation dynamique. Gardez une trace de l'actuel et du précédent (bénéfice, date d'achat et date de vente) Si le courant est plus élevé que le précédent, remplacez le précédent par le courant.

    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 );
    }   

voici ma solution 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);     
}

J'ai trouvé une solution simple - le code est plus explicite. C'est l'une de ces questions de programmation dynamique.

Le code ne prend pas en charge la vérification des erreurs et les cas extrêmes. C'est juste un exemple pour donner l'idée de la logique de base pour résoudre le problème.

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;

    }

Voici ma solution. modifie l'algorithme de sous-séquence maximum. Résout le problème en O (n). Je pense que cela ne peut pas être fait plus rapidement.

C'est un problème intéressant, car il semble difficile, mais une réflexion approfondie aboutit à une solution élégante et épurée.

Comme cela a été noté, il peut être résolu par force brute en temps O (N ^ 2). Pour chaque entrée du tableau (ou de la liste), parcourez toutes les entrées précédentes pour obtenir le minimum ou le maximum selon que le problème est de trouver le gain ou la perte le plus élevé.

Voici comment réfléchir à une solution en O (N): chaque entrée représente un nouveau max (ou min) possible. Ensuite, tout ce que nous devons faire est de sauvegarder le min (ou max) précédent, et de comparer le diff avec le courant et le min (ou max) précédent. Peasy facile.

Voici le code, en Java comme test 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;
    }

}

Dans le cas du calcul de la plus grande perte, nous gardons une trace du maximum dans la liste (prix d'achat) jusqu'à l'entrée actuelle. Nous calculons ensuite la différence entre le max et l'entrée courante. Si max - current> maxLoss, alors nous gardons ce diff comme le nouveau maxLoss. Puisque l'indice de max est garanti inférieur à l'indice actuel, nous garantissons que la date «d'achat» est inférieure à la date de «vente».

Dans le cas du calcul du gain le plus élevé, tout est inversé. Nous gardons une trace du min dans la liste jusqu'à l'entrée actuelle. Nous calculons le diff entre le min et l'entrée courante (en inversant l'ordre dans la soustraction). Si current - min> maxGain, nous conservons cette différence comme nouveau maxGain. Encore une fois, l'indice de «acheter» (min) vient avant l'indice de courant («vendre»).

Nous avons seulement besoin de garder une trace du maxGain (ou maxLoss), et de l'indice de min ou max, mais pas les deux, et nous n'avons pas besoin de comparer les indices pour valider que `` acheter '' est inférieur à `` vendre '', car nous obtenez cela naturellement.

Bénéfice maximal de vente unique, solution 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
}

Voici un projet qui effectue des tests de complexité temporelle sur les approches o (N) vs o (n ^ 2) sur un ensemble de données aléatoires sur 100k pouces. O (n ^ 2) prend 2 secondes, tandis que O (n) prend 0,01 s

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
}

C'est l'approche la plus lente, o (n ^ 2) qui parcourt le reste des jours pour chaque jour, double boucle.

La réponse aux votes les plus élevés ne permet pas les cas dans lesquels le profit maximum est négatif et devrait être modifiée pour permettre de tels cas. On peut le faire en limitant la plage de la boucle à (len (a) - 1) et en modifiant la manière dont le profit est déterminé en décalant l'indice de un.

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

Comparez cette version de la fonction avec la précédente pour le tableau:

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");
}

Une possibilité pour déterminer le profit maximum pourrait être de garder une trace des éléments minimum du côté gauche et maximum du côté droit dans le tableau à chaque index du tableau. Lorsque vous parcourez ensuite les cours des actions, pour un jour donné, vous connaîtrez le prix le plus bas jusqu'à ce jour, et vous connaîtrez également le prix maximum après (et y compris) ce jour-là.

Par exemple, définissons un min_arret max_arr, avec le tableau donné arr. Index iin min_arrserait l'élément minimal in arrpour tous les indices <= i(à gauche et y compris i). Index iin max_arrserait l'élément maximum in arrpour tous les indices >= i(à droite et y compris i). Ensuite, vous pourriez trouver la différence maximale entre les éléments correspondants dans max_arret `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

Cela devrait fonctionner dans le temps O (n), mais je pense que cela utilise beaucoup d'espace.

C'est la différence maximale entre deux éléments du tableau et voici ma solution:

Complexité temporelle O (N) Complexité spatiale O (1)

    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);

Après avoir échoué à un examen de codage en direct pour un poste d'ingénieur en solutions FB, j'ai dû le résoudre dans une atmosphère calme et fraîche, alors voici mes 2 cents:

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);

La seule réponse qui répond vraiment à la question est celle de @akash_magoon (et de manière si simple!), Mais elle ne renvoie pas l'objet exact spécifié dans la question. J'ai un peu refacturé et j'ai ma réponse en PHP renvoyant exactement ce qui est demandé:

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];
}

Une solution soignée:

+ (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))

Ce programme en python3 peut renvoyer le prix d'achat et le prix de vente qui maximiseront le profit, calculé avec la complexité temporelle de O (n) et la complexité spatiale de O (1) .

Voici ma solution

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;
 }
}

Pour toutes les réponses gardant une trace des éléments minimum et maximum, cette solution est en fait une solution O (n ^ 2). En effet, à la fin, il faut vérifier si le maximum s'est produit après le minimum ou non. Dans le cas où ce ne serait pas le cas, d'autres itérations sont nécessaires jusqu'à ce que cette condition soit remplie, ce qui laisse le pire des cas de O (n ^ 2). Et si vous voulez sauter les itérations supplémentaires, il faut beaucoup plus d'espace. Quoi qu'il en soit, un non-non par rapport à la solution de programmation dynamique