题目描述

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.

题目思路

• 定义 max 为当卖出价为数组中第 i 个数字时可能获得的最大利润。显然，在卖出价固定时，买入价越低获得的利润越大。也就是说，如果在扫描到数组中的第 i 个数字时，只要我们能够记住之前的 i-1 个数字中的最小值，就能算出在当前价位卖出时可能得到的最大利润
• <剑指Offer>面试题63: 股票的最大利润

代码 C++

• 思路一、

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() < 2){
            return 0;    
        }
        
        int max = 0;
        int min = prices[0];
        
        for(int i=1; i < prices.size(); i++){
            if(i == 1){
                if(min < prices[i]){
                    max = prices[i] - min;
                }
            }
            else{
                if(min > prices[i-1]){
                    min = prices[i-1];
                }
                max = prices[i]-min >  max? prices[i]-min : max;
            }
        }
        return max;
    }
};

• 思路二、动态规划

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

总结展望