(LeetCode-数组-1) 买卖股票的最佳时机[通俗易懂]

1.买卖股票的最佳时机

假设你有一个数组，其中第 i 个元素是一支给定股票第 i 天的价格。如果您只能完成最多一笔交易（即买入和卖出一股股票），则设计一个算法来找到最大的利润。

输入: [7, 1, 5, 3, 6, 4]
输出: 5

最大利润 = 6-1 = 5（不是 7-1 = 6, 因为卖出价格需要大于买入价格）

分析:
1.只能交易一笔
2.变量current为买入价格，max为最大利润
3.低则买入，高则卖出

int maxProfit(vector<int>& prices) {
        if(prices.empty())return 0;
        int max=0,current=prices[0];
        for(int i=1;i<prices.size();i++){
        if(current>prices[i]){
            current=prices[i];
        }else{
            int sum=prices[i]-current;
            if(sum>max)max=sum;
        }
        }
        return max;
}

2.买卖股票的最佳时机 II

假设有一个数组，它的第 i 个元素是一个给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。

分析:
1.可以交易多笔
2.相邻价格中，只要后一次比前一次高，就买入

int maxProfit(vector<int>& prices) {
     if(prices.empty())return 0;
       int max = 0;
       for(int i=1; i<prices.size(); i++) {
         if(prices[i] - prices[i-1] > 0) {
              max += (prices[i] - prices[i-1]);
         }
     }
     return max;
}

3.买卖股票的最佳时机 III

假设你有一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。你不可同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析:
1.最多可以进行两笔交易
2.将数组分为左右两个子数组，分别求出对应的最大利润

int maxProfit(vector<int>& prices) {
            if(prices.empty())return 0;
            int min=prices.front(),max=prices.back(),size=prices.size();
            vector<int> left(size,0);
            vector<int> right(size,0);
            for(int i=1;i<size;i++){
            if(prices[i]>min){
                left[i]=(prices[i]-min)>left[i-1]?(prices[i]-min):left[i-1];
            }else{
                left[i]=left[i-1];
                min=prices[i];
            }
    }
    for(int i=size-2;i>=0;i--){
        if(prices[i]<max){
            right[i]=(max-prices[i])>right[i+1]?(max-prices[i]):right[i+1];
        }else{
            right[i]=right[i+1];
            max=prices[i];
        }
    }
    int result=0;
    for(int i=0;i<size;i++){
        result=(right[i]+left[i])>result?(right[i]+left[i]):result;
    }
    return result;
}