###### tags: `Leetcode` `easy` `dynamic programming` `python` `c++` `Top 100 Liked Questions`

# 121. Best Time to Buy and Sell Stock

## [題目來源: ]https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

## 題目:
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a **single day** to buy one stock and choosing a **different day in the future** to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

## 解題思路:
兄弟題目: [122. Best Time to Buy and Sell Stock II](/nOzARxUKRl-R9qKhT-1HLQ)
* 每次比較最小買的價格，並更新獲利

## Python:

class Solution(object):
    def maxProfit(self, prices):
        profit = 0
        buy = 100000
        for i in range(len(prices)):
            buy=min(buy, prices[i])
            profit=max(profit, prices[i]-buy)
        return profit

if __name__ == '__main__':
    result = Solution()
    prices = [7,1,5,3,6,4]
    ans = result.maxProfit(prices)
    print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res={1};
        for (int i=0; i<rowIndex; i++){
            for (int j=res.size()-1; j>0; j--){
                res[j]+=res[j-1];
            }
            res.push_back(1);
        }
        return res;
    }
};

int main(){
    Solution res;
    vector<int>ans=res.getRow(4);
    for (int i=0; i<ans.size(); i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}