[arrays] 최대 단일 판매 수익

나는이 문제를 사랑한다. 이것은 고전적인 인터뷰 질문이며 어떻게 생각 하느냐에 따라 더 나은 해결책을 얻게 될 것입니다. O (n ² ) 시간 보다 더 나은 시간 에이 작업을 수행하는 것이 확실히 가능하며 여기에 문제에 대해 생각할 수있는 세 가지 방법을 나열했습니다. 이 질문에 대한 답변이 되었기를 바랍니다.

첫째, 분할 정복 솔루션입니다. 입력을 반으로 나누고 각 하위 배열의 문제를 해결 한 다음 두 가지를 결합하여이 문제를 해결할 수 있는지 봅시다. 우리가 실제로 이것을 할 수 있고 그렇게 효율적으로 할 수 있다는 것이 밝혀졌습니다! 직감은 다음과 같습니다. 하루가있는 경우 가장 좋은 방법은 그날 구매 한 다음 같은 날 다시 팔아서 이익을 내지 않는 것입니다. 그렇지 않으면 배열을 두 개로 나눕니다. 최적의 답이 무엇인지 생각해 보면 다음 세 위치 중 하나에 있어야합니다.

1. 올바른 매수 / 매도 쌍은 전반기에 완전히 발생합니다.
2. 올바른 매수 / 매도 쌍은 하반기에 완전히 발생합니다.
3. 올바른 매수 / 매도 쌍은 두 절반 모두에서 발생합니다. 우리는 전반기에 구매 한 다음 후반기에 판매합니다.

우리는 첫 번째와 두 번째 절반에서 알고리즘을 재귀 적으로 호출하여 (1)과 (2)의 값을 얻을 수 있습니다. 옵션 (3)의 경우, 가장 높은 수익을내는 방법은 상반기에는 가장 낮은 지점에서 매수하고 하반기에는 가장 높은 지점에서 판매하는 것입니다. 입력에 대한 간단한 선형 스캔을 수행하고 두 값을 찾는 것만으로 두 반쪽에서 최소값과 최대 값을 찾을 수 있습니다. 그러면 다음과 같은 반복 알고리즘이 제공됩니다.

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

마스터 정리 를 사용하여 반복을 해결하면 이것이 O (n lg n) 시간에 실행되고 순환 호출에 O (lg n) 공간을 사용할 것임을 알 수 있습니다. 우리는 순진한 O (n ² ) 솔루션을 이겼습니다 !

하지만 기다려! 우리는 이것보다 훨씬 더 잘할 수 있습니다. 반복에 O (n) 항이있는 유일한 이유는 각 절반에서 최소값과 최대 값을 찾으려고 전체 입력을 스캔해야했기 때문입니다. 우리는 이미 각 반을 재귀 적으로 탐색하고 있기 때문에, 아마도 재귀가 각 반에 저장된 최소값과 최대 값을 돌려 주도록함으로써 더 잘할 수있을 것입니다! 즉, 우리의 재귀는 다음 세 가지를 되돌려줍니다.

1. 수익을 극대화하기위한 구매 및 판매 시간입니다.
2. 범위의 전체 최소값입니다.
3. 범위의 전체 최대 값입니다.

이 마지막 두 값은 계산할 재귀와 동시에 실행할 수있는 간단한 재귀를 사용하여 재귀 적으로 계산할 수 있습니다 (1).

1. 단일 요소 범위의 최대 값과 최소값은 해당 요소 일뿐입니다.
2. 다중 요소 범위의 최대 값과 최소값은 입력을 절반으로 나누고 각 절반의 최대 값과 최소값을 찾은 다음 각각의 최대 값과 최소값을 가져 와서 찾을 수 있습니다.

이 접근 방식을 사용하면 이제 반복 관계가

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

여기에서 마스터 정리를 사용하면 O (lg n) 공간이있는 O (n)의 런타임이 제공됩니다. 이는 원래 솔루션보다 훨씬 낫습니다!

하지만 잠깐만 요-우리는 이것보다 더 잘할 수 있습니다! 동적 프로그래밍을 사용하여이 문제를 해결하는 것에 대해 생각해 봅시다. 아이디어는 다음과 같이 문제에 대해 생각하는 것입니다. 처음 k 개 요소를 살펴본 후 문제에 대한 답을 알고 있다고 가정합니다. 첫 번째 (k + 1) 요소에 대한 문제를 해결하기 위해 초기 솔루션과 결합 된 (k + 1) 첫 번째 요소에 대한 지식을 사용할 수 있습니까? 그렇다면 첫 번째 요소에 대해 계산할 때까지 첫 번째 요소, 처음 두 개, 처음 세 개 등의 문제를 해결하여 훌륭한 알고리즘을 얻을 수 있습니다.

이를 수행하는 방법에 대해 생각해 봅시다. 요소가 하나만있는 경우 최상의 구매 / 판매 쌍이어야한다는 것을 이미 알고 있습니다. 이제 우리가 처음 k 개 요소에 대한 최선의 답을 알고 있고 (k + 1) 번째 요소를 본다고 가정합니다. 그러면이 값이 첫 번째 k 요소에 대해 가졌던 것보다 더 나은 솔루션을 생성 할 수있는 유일한 방법은 첫 번째 k 요소 중 가장 작은 요소와 해당 새 요소의 차이가 지금까지 계산 한 가장 큰 차이보다 큰 경우입니다. 따라서 요소를 살펴보면서 지금까지 살펴본 최소값과 첫 번째 k 요소만으로 얻을 수있는 최대 수익이라는 두 가지 값을 추적한다고 가정합니다. 처음에는 지금까지 본 최소값이 첫 번째 요소이고 최대 이익은 0입니다. 새로운 요소를 보면 우리는 먼저 지금까지 보았던 최저 가격으로 구매하고 현재 가격으로 판매하여 얼마나 벌 수 있는지 계산하여 최적의 수익을 업데이트합니다. 이것이 지금까지 계산 한 최적 값보다 낫다면 최적의 솔루션을이 새로운 수익으로 업데이트합니다. 다음으로 지금까지 본 최소 요소를 현재 가장 작은 요소와 새 요소의 최소값으로 업데이트합니다.

각 단계에서 우리는 O (1) 작업 만 수행하고 n 개의 요소를 정확히 한 번 방문하므로 완료하는 데 O (n) 시간이 걸립니다! 또한 O (1) 보조 기억 장치 만 사용합니다. 이것은 우리가 지금까지 얻은 것만 큼 좋습니다!

예를 들어 입력에서이 알고리즘이 실행되는 방법은 다음과 같습니다. 배열의 각 값 사이에있는 숫자는 해당 지점에서 알고리즘이 보유한 값에 해당합니다. 실제로이 모든 것을 저장하지는 않지만 (O (n) 메모리가 필요합니다!), 알고리즘이 진화하는 것을 보는 것은 도움이됩니다.

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

답 : (5, 10)

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

답 : (4, 12)

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

답 : (1, 5)

이제 더 잘할 수 있습니까? 불행히도 점근 적 의미가 아닙니다. O (n) 시간 미만을 사용하면 큰 입력에서 모든 숫자를 볼 수 없으므로 최적의 답을 놓치지 않는다고 보장 할 수 없습니다 (요소에서 “숨길”수 있습니다. 보지 않았다). 또한 O (1) 공간보다 작은 공간을 사용할 수 없습니다. big-O 표기법에 숨겨진 상수 요소에 대한 최적화가있을 수 있지만 그렇지 않으면 근본적으로 더 나은 옵션을 찾을 수 없습니다.

전반적으로 이것은 다음과 같은 알고리즘이 있음을 의미합니다.

• Naive : O (n ² ) 시간, O (1) 공간.
• 나누기 및 정복 : O (n lg n) 시간, O (lg n) 공간.
• 최적화 된 분할 및 정복 : O (n) 시간, O (lg n) 공간.
• 동적 프로그래밍 : O (n) 시간, O (1) 공간.

도움이 되었기를 바랍니다!

편집 : 관심이 있다면 이 네 가지 알고리즘의 Python 버전을 코딩하여 함께 놀아보고 상대적 성능을 판단 할 수 있습니다. 코드는 다음과 같습니다.

# 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

답변

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

}

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

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

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;

    }