【LeetCode】 121. Best Time to Buy and Sell Stock

Description

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.

給你一個陣列代表，每個元素代表第i天的物價。

如果你只能得到一次的價差(只做一次買和賣)，請設計一個演算法找到最大利潤。

注意你不能在買之前就賣一個東西。

Example:

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.

Solution

• 記住兩個變數：現階段最低價格和現階段最大利潤。
• ForLoop跑每個元素，先計算最大利潤，再更新最低價格。

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price=9999;
        int max_profit=0;
        for(int i=0;i<prices.size();i++)
        {
            max_profit = max(prices[i]-min_price,max_profit);
            min_price = min(min_price,prices[i]);
        }
        return max_profit;
    }
};

tags: LeetCode C++