[2018-11-18] [LeetCode-Week11] 121. Best Time to Buy and Sell Stock 动态规划

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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
Explanation: In this case, no transaction is done, i.e. max profit = 0.

思路：显然暴力是 O(n2) 的算法
所以肯定是 O(n) 才不会超时
考虑只能扫描一次，那么我们对于每个新值，比较他和之前决定的购买日的值，如果比其小，那么直接将新的购买日设为这天（后面的肯定这样才赚）。如果比其小，那么考虑将其设为卖出日，看是否比之前更赚，如果更赚，更新答案即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        
        int ans = 0;
        int buy = 0;
        
        for (int i = 1; i < n; i++) {
            int nans = prices[i] - prices[buy];
            if (prices[i] < prices[buy]) {
                buy = i;
            } else if (nans > ans) {
                ans = nans;
            }
        }
        
        return ans;
    }
};