Easy
Related Topics: Array / Dynamic Programming
LeetCode Source

解題想法

當下想到最直覺的解法，一個變數 min_index 紀錄最小值的位置，i 用來尋訪每個的 prices 的值

for loop 裡頭判斷式用來找尋最佳解

• if prices[i] < prices[min_index] 找尋最小值得位置
• if i > min_index and prices[i] - prices[min_index] > res 找 res 最佳解

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_index, res = 0, 0
        for i in range(1, len(prices)):
            if prices[i] < prices[min_index]:
                min_index = i
            if i > min_index and prices[i] - prices[min_index] > res:
                res = prices[i] - prices[min_index]
        return res

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0, min_index = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] < prices[min_index])
                min_index = i;
            if (i > min_index && prices[i] - prices[min_index] > res)
                res = prices[i] - prices[min_index];
        }
        return res;
    }
};

這系列文被記錄在 Top Interview 150 Series