[LeetCode]--121. Best Time to Buy and Sell Stock

  1. 云栖社区>
  2. 博客>
  3. 正文

[LeetCode]--121. Best Time to Buy and Sell Stock

yexx 2016-10-05 16:26:00 浏览756
展开阅读全文

Say you have an array for which the ith 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.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

思路首先:动态规划
遍历数组时记录当前价格以前的最小价格curMin,记录昨天能够获得的最大利润maxProfit。对于今天,为了能获得此刻的最大利润,显然只能卖,或者不做任何操作。如果不做任何操作,显然还是昨天maxProfit。如果卖掉今天天的股票,显然prices[i]-curMin。

public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int minPro = prices[0];
        int maxGap = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - minPro > maxGap)
                maxGap = prices[i] - minPro;
            if (prices[i] < minPro)
                minPro = prices[i];
        }
        return maxGap;
    }

网友评论

登录后评论
0/500
评论
yexx
+ 关注