Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

 

 

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.

Naive Way: 这道题是课本DP那章的一道原题，我才想起来我当时做过。于是就用DP做了。
基本逻辑为
opt[i] //表示第ii所能获得的最大利润
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[i-1], p[i] - min)

因为不需要内层循环访问之前的opt, 看来O(1)的space就足够了。

public int maxProfit(int[] prices) {
        if(prices.length==0){return 0;}
        int opt = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            opt = Math.max(opt, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return opt;
    }