121. Best Time to Buy and Sell Stock.md

121. Best Time to Buy and Sell Stock

Problem

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

tag:

• dp

Solution

双指针法

profit[i] = prices[i]-min(prices[j] j<i)
max(profit[i], i=1...n)

即： 第i天卖出的最大利润 = prices[i] - i天之前买入的最低价格
     最大利润 = 1,2,3...n天卖出利润最大的一个

java

    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, profit = 0;
        for(int i=0; i<prices.length; i++) {
            if (prices[i]<min) 
                min = prices[i];
            if(prices[i]-min > profit) 
                profit = prices[i]-min;
        }
        return profit;
    }

go

     func maxProfit(prices []int) {
          min := math.MaxInt
          maxProfit := 0
          for i:=0; i<len(prices); i++) {
               if prices[i]-min > maxProfit {
                    maxProfit = prices[i]-min
               }
               if prices[i] < min {
                    min = prices[i]
               }
          }
          return maxProfit
     }