CareerCup

void StockProcess(const vector<int>& stocks,
                                  int* buyday,
                                  int* sellday)
{
        int min_index = 0;
        *buyday = 0;
        *sellday = 0;
        for (int i = 1; i < stocks.size(); ++i) {
              if (stocks[i] < stocks[min_index]) {
                    min_index = i;
              } else if ( (stocks[i] - stocks[min_index]) > (stocks[*sellday] - stocks[*buyday])) {
                   *buyday = min_index;
                   *sellday = i;
             }
        }
}

Time Complexity: O(n)

Assuming stock is always positive int. buy and sell are -1s if stock is always losing.

void BestDaysToSell(int []days, out int buy, out int sell)
{

	int buy = -1;
	int sell= -1;
	int currBuy = days[0];
	int currSell= int.MinValue;

	for(int i=1;i<days.Length; i++)
	{
		if(days[i] < currbuy)
		{
			currSell=days[i]
			currBuy = days[i];
		}
		else if(days[i] > currSell)
		{
			currSell = days[i];
			if(days[i] - currBuy > sell - buy)
			{
				buy = currSell;
				sell = currBuy;
			}
		}
	}
}

maxProfit( int stockPrice[] , int N )
{
      int buyPrice = stockPrice[0];
      int sellPrice =-1;
      int profit =0 ;
      for( i=1;i<N;i++ )
      {
           int price = stockPrice[i];
           
           if( price - buyPrice > profit )
           {
               profit = price - buyPrice ;
               sellPrice = price ;
           } 
           
           buyPrice = min(buyPrice , price );
      } 
}

Using a MinStack, that is, a stack with push, pop and min operations having O(1) complexity. This runs in O(n).

public class MaximizeProfit {

	public int maximize(Integer[] stockPrice){
		int maxProfit=0;

		MinStack<Integer> stack = new MinStack<Integer>();
		stack.push(stockPrice[0]);
		
		for(int i=1; i<stockPrice.length; i++){
			if( (stockPrice[i] - stack.min()) > maxProfit ) {
				maxProfit = stockPrice[i] - stack.min();
			}
			// stack.min() will return the minimum element from 0 to i-1
			stack.push(stockPrice[i]); 
		}
		return maxProfit;
	}
}

For people who are interested. The same problem in there in CLRS book, "maximum-subarray problem". O(nlgn) complexity.

def maximizeProfit(input):
    
    maxDiff = float("-inf") 
    currentDiff = float("-inf")
    bottom = input[0]
    max = 0
    for index in range(1,len(input)):
        currentDiff += input[index] - input[index-1]
        
        if (currentDiff > maxDiff):
            maxDiff = currentDiff
            max = input[index]
            
        if (bottom > input[index]):
            print(currentDiff)
            bottom = input[index]
            currentDiff = 0
        
    print("buy at :"+str(max -  maxDiff)+ " Sell at: "+str(max))

Refer cormen. Longest common sub sequence. O(NlogN)

assuming profit is in positive and loss is in negative,this problem becomes same as of finding largest subarray in an array