CareerCup

public static int maxProfit(int[] prices, int fee) { 
              if(prices.length==0)
                  return 0;
        int min=0;
        int max=0;
        int curprofit=0;
        int prevprofit=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[max]){
                if(prices[i]-prices[min]-fee>=0){
                curprofit= prevprofit + prices[i]-prices[min]-fee;
                }
                max=i;
            }
            else if(prices[i]<=prices[max]){
                min=i;
                prevprofit= curprofit;
                max=i;
            }
        }
        return curprofit;
}

I could only do it in O(n^2). I am sure we can do it in O(n).

import java.util.Map;
		import java.util.HashMap;

		public class StockMaximumProfit {
			public static void main(String[] args) {
				int prices[] = new int[] {2, 30, 15, 10, 8, 25, 80};
				 Map<Integer, Integer> bestBuySellCombination = new 	
										HashMap<Integer, Integer> ();
                		int maximumPriceDifference = 0;
 		                int temporaryPriceDifference = 0;
                		int min = 0;

				for (int i=0; i<prices.length; i++) {
                        		for (int j=i+1; j<prices.length; j++) {
 		                                if (prices[j] > prices[i]) {
		                                        if (prices[j] >= min) {
                		                                min = prices[j];
								temporaryPriceDifference = prices[j] - prices[i];
			                                        if (temporaryPriceDifference > 
									maximumPriceDifference) {
                                                        			maximumPriceDifference = 
											temporaryPriceDifference;
	 			                                                        bestBuySellCombination.
												put(prices[i],prices[j]);
                                               	 		}
                                        		} else {
								min = 0;
								break;
							}
					} else {
						break;
					}
			}
	}

			for (Map.Entry<Integer, Integer> itr : bestBuySellCombination.entrySet()) {
                        	System.out.println("Best combinations are: " + itr.getKey() + " and " + itr.getValue());
                        	System.out.println("The difference being: " + (itr.getValue() - itr.getKey()));
                	}
        	}
	}

def maxProfit(prices, fee):
sum = lower = 0
for i,p in enumerate(prices + [-1]):
if i == 0:
continue
if p < prices[i - 1]:
if prices[i - 1] - fee > prices[lower]:
sum += prices[i - 1] - prices[lower] - fee
lower = i
return sum

print maxProfit([1,2,3,1,5,1,7], 1)