CareerCup

Keep track of minimum from left to right and take the difference with the current stock[i]. If it is greater than maxprofit, then update the maxprofit. Repeat it with all the stock values while going from left to right.

int getMaxProfit(int *a, int n)
{
	int maxProfit = 0;
	int minStockSoFar = a[0];

	for(int i=1; i<n; i++)
	{
		maxProfit = max( maxProfit, a[i] - minStockSoFar );
		minStockSoFar = min( minStockSoFar, a[i] );
	}

	return maxProfit;
}

Time complexity: O(n)
Space : O(1)

Could you clarify your question please?

This question was a little hard to read. The question does say the stock is sold n days after the stocks is purchased. So you need to keep track of a running max that is price[today] - price[n days later]

Here is a solution in php:

$prices = array(20,50,52,10,45,34, 100);

function getMaxProfit($prices, $n) {
  $maxProfit = 0; //assume there is a profitable day possible
  $bestDay = 0;

  for ($i=0; $i < (sizeof($prices) - $n); $i++) {
     $todayProfit = $prices[$i+$n] - $prices[$i];
     echo $todayProfit . PHP_EOL;
     if ($todayProfit > $maxProfit) {
        $maxProfit = $todayProfit;
        $bestDay = $i;
     }
  }
  return $bestDay + 1; //days should start with	1
}

echo getMaxProfit($prices, 3);

pair<int, int> bestbuyoutprice(int A[], int size, int &maxprofit)
{
	int min = A[0];
	int tempmin = min;
	int max = A[0];
	int currentprofit = 0;
	maxprofit = 0;
	for (int i = 0; i < size; i++)
	{
		if (A[i] < min)
		{
			tempmin = A[i];
			currentprofit = 0;
		}
		else
		{
			currentprofit = A[i] - tempmin;
			if (currentprofit > maxprofit)
			{
				maxprofit = currentprofit;
				max = A[i];
				min = tempmin;
			}
		}
	}
	return make_pair(min,max);
}
void main (int argc, char** argv)
{
	int A[] = {20,50,52,10,45,34, 5};
	int size = sizeof(A)/sizeof(int);
	int profit;
	pair<int, int> res = bestbuyoutprice(A, size, profit);

	for ( int i = 0; i < size; i++)
		cout<<A[i]<<",";
	cout<<endl;
	cout<<"min:"<<res.first<<" max:"<<res.second<<" profit:"<<profit<<endl;
	_getch();
}

private static int[] profits = null;
private static bool[] calculated = null;
public static int CalculateProfit(int []prices, int index, int []profits)
{
if (prices.Length - index <= 1 ) return 0;
int curPrice = prices[index];
int maxValue = 0; int value=0;
for (int i = index + 1; i < prices.Length; ++i)
{
value = prices[i] - curPrice;
if (i + 1 != prices.Length && !calculated[i+1])
{
profits[i+1] = CalculateProfit(prices, i+1, profits);
value = value + profits[i + 1];
}

if(value> maxValue)
maxValue =value;
}
if (profits[index + 1] > maxValue)
maxValue = profits[index + 1];
return maxValue;
}

static void Main(string[] args)
{
// 20, 50, 52,
int[] prices = new int[] { 20, 50, 52, 10, 45, 35 ,36, 45};
profits = new int[prices.Length];
calculated = new bool[prices.Length];
int value = CalculateProfit(prices, 0, profits);
Console.WriteLine("Value:"+value);
}

Hi, it has been some time already, but you may find exactly the same problem in the Cormen's famous book, where he simplifies the problem to finding maximum sum, by converting the stock values to it's day to to day changes.

def computeMaxProfitBuySell(ll=None):
    lst = ll or [20,50,52,10,45,34]
    maxProfit = 0
    i=0
    for j in xrange(1,len(lst)):
        print maxProfit, i,j
        if lst[i] < lst[j]:
            profit = lst[j] - lst[i]
            if profit > maxProfit:
                maxProfit = profit
        else:
            #lst[i] < lst[j], so bring i to j
            i=j
    
    return maxProfit

print computeMaxProfitBuySell()

have i at zero'th element. Everytime lst[j] > lst[i], compute profit and assign to max profit if profit > max profit,
everytime, lst[i]< lst[j], bring i to j
xrange/range ensures, j increments by 1 every loop