黄金投资

很简单的题目，不知道为什么没有人抄近道。
最多买卖两次且两次买卖没有交集，因此维护前缀最大差，后缀最大差，并枚举分割点即可。复杂度O(n)。

class Solution:
    def maxProfit(self , prices ):
        n = len(prices)
        prices = [0] + prices
        pred = [0] * (n + 5)
        suff = [0] * (n + 5)
        MiN = 100000000
        for i in range(1, n + 1) :
            pred[i] = max(pred[i - 1], prices[i] - MiN)
            MiN = min(MiN, prices[i])
        MaX = -100000000
        for i in range(n, 0, -1) :
            suff[i] = max(suff[i + 1], MaX - prices[i])
            MaX = max(MaX, prices[i])
        ans = 0
        for i in range(1, n + 1) :
            ans = max(ans, pred[i] + suff[i + 1])
        return ans

class Solution {
public:
    /**
     * 黄金投资
     * @param prices int整型一维数组 价格
     * @param pricesLen int prices数组长度
     * @return int整型
     */
    int maxProfit(int* prices, int pricesLen) {
        // write code here
        int interest=0;
        int max=0;
        for(int i=0;i<pricesLen;i++){
            for(int j=i;j<pricesLen;j++){
                for(int k=j;k<pricesLen;k++){
                    for(int l=k;l<pricesLen;l++){
                        
                        interest=prices[j]-prices[i]+prices[l]-prices[k];
                        if(max<interest){
                            max=interest;
                        }
                    }
                }
            }
        }
        return max;
    }
};

LeetCode 买卖股票的最佳时机 III

class Solution {
public:
    int maxProfit(int* prices, int pricesLen) {
        int buy1 = INT_MIN, sell1 = 0;
        int buy2 = INT_MIN, sell2 = 0;
        for (int i = 0; i < pricesLen; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

public int maxProfit(int[] prices)
{ int n = prices.length;  int[] pred = new int[n];  int[] suff = new int[n];  int min = prices[0];  int max = prices[n-1];  //从前往后递归，每个pred[i]表示到i为止，最大的收益  for (int i = 1; i < n; i++) {
        pred[i] = Math.max(pred[i-1],prices[i]-min);
       min = Math.min(min,prices[i]);  } //从后往前，每个suff[i]表示从n-1 到 i 为止的最大收益  for (int i=n-2;i>=0;i--)
    {
        suff[i] = Math.max(suff[i+1],max-prices[i]);  max = Math.max(max,prices[i]);  } int ans = 0;  //pred[i]+ suff[i]表示0-i，i-n-1这两段的最大收益的和  for (int i=0;i<n;i++)
    {
        ans = Math.max(ans,pred[i]+suff[i]);  } return ans; }

class Solution {
public:
    /**
     * 黄金投资
     * @param prices int整型一维数组 价格
     * @param pricesLen int prices数组长度
     * @return int整型
     */
    int maxProfit(int* prices, int pricesLen) {
        // write code here
        // 1 - 准备阶段
        vector<int> maxDict;

        
        // 2 - 得到结果
        // 得到第一个差距最大的增序列
        int maxPro1 = 0;
        int left = 0, right = 0;
        while(right<pricesLen){
            if(right+1<pricesLen && prices[right]<=prices[right+1]){
                right++;
            }else if(right+1 == pricesLen){
                maxDict.push_back(prices[right]-prices[left]);
                right++;
            }else{
                maxDict.push_back(prices[right]-prices[left]);
                right++;
                left = right;
            }
        }
        sort(maxDict.begin(), maxDict.end(), greater<int>());
        
        // 3 - 输出结果
        return maxDict[0]+maxDict[1];
    }
};