LeetCode #121: Best Time to Buy

Problem

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.

题意

怀疑智商题之二：又是买股票和卖股票的问题。题目给定一个数组prices,prices[i]代表第i天股票的价格。要求找出最大利润。
限制条件是，在这n天中只能完成一次买入和卖出操作。（Best Time to Buy an Sell Stock II中，可无限次买入和卖出）。

分析

初始化minPrice = 0, maxPro = 0。
从第0天开始，通过for循环遍历数组，在访问prices[i]时，做两次比较：

• 第一次比较prices[i]和当前minPrice的值
• 第二次比较prices[i] - minPrice和当前maxPro

这道题中要说明其DP思想是一件让人很为难的事情···简单来说，这道题是从第一天开始，逐步扩大问题规模，记录出现过的最低价格，每一天的价格都记录一个利润值，比较该利润值与到目前为止的最大利润值，更新最大利润值，直到问题规模增长到n为止。

Code

//Runtime: 6ms
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int minPrice = prices[0];
        int maxPro = 0;
        for (int i = 0; i < prices.size(); i++){
            minPrice = min(minPrice, prices[i]);
            maxPro = max(maxPro, prices[i] - minPrice);
        }

        return maxPro;
    }
};