Best Time to Buy and Sell Stock 买卖股票最佳时间系列

第一题只能完成一次交易，求最大收益？解法类似于最大的连续子数组和，区别在于连续子数组的和取决于当前元素与当前元素加上之前连续和的最大值，股票的买卖的价位只取决于递增子数组中右边最大减去左边最小的值，但是我们依然可以用连续的思想去解题，如果子数组递增，那么我们只需要把数组相连元素的差求和，与只允许买卖一次的利润是一样的，这里就利用到了DP的思维，如果子数组在中间有减小的趋势，那么我们势必应该从更小的值开始累加能够得到全局最优利润，累加和应该清0，然后重新累加，取整个过程最大值

// 最大连续子数组和
// https://leetcode.com/problems/maximum-subarray/
int maxSubArray(vector<int>& nums) {
    int maxCur=nums[0];
    int maxSofar=nums[0];

    for(int i=1;i<nums.size();++i) {
        maxCur = max(nums[i], maxCur+nums[i]);
        maxSofar = max(maxCur, maxSofar);
    }
    return maxSofar;
}

稍加修改即得到本题的解法

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

第二题允许交易任意次，求最大利润？没有限制那么我们就可以使用贪心的方式，只要有任何利润，赚就完事了

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

第三题只能最多完成 2 次交易，依然求最大利润？类似于一种赌徒的心态，假如说我们第一次赚了 10 元，我们不会就这样走人，如果股票的价格为 10 元，我们依然会买入，说不定下次就能赚更多呢？基于这种多阶段贪心的思维，我们依然可以这样来解题，把希望都寄托在最后卖出的利润上

int maxProfit(vector<int>& prices) {
    int hold1=INT_MIN;
    int release1=0;
    int hold2=INT_MIN;
    int release2=0;

    for(auto p : prices) {
        release2=max(release2, hold2+p);
        hold2=max(hold2, release1-p);
        release1=max(release1, hold1+p);
        hold1=max(hold1, -p);
    }
    return release2;
}

或者用常规的 DP 方法也可以 T[i][j] = max(T[i-1][j], T[i-1][m] + price[j] - price[m]) ，m ∈[0, j-1]

int maxProfit(vector<int>& prices) {
    int len=prices.size();
    if (len<2) return 0;
    int dp[3][len];
    memset(dp, 0, sizeof dp);

    for(int i=1;i<3;++i) {
        for(int j=1;j<len;++j) {
            int maxCur=INT_MIN;
            for(int m=0;m<j;++m)
                maxCur=max(maxCur, dp[i-1][m]-prices[m]);
            dp[i][j]=max(dp[i][j-1], prices[j]+maxCur);
        }
    }
    return dp[2][len-1];
}

第四题可以买卖 K 次，注意 K 的范围，如果 K x 2 大于价目长度，可以直接贪心解决，否则同样使用第三题的 DP 方程，提取公因式，减少计算量，解法如下

int maxProfit(int k, vector<int>& prices) {
    int len=prices.size();
    if (len<2) {
        return 0;
    } else if ((len>>1) < k) {
        return quickSolve(k, prices);
    }
    int dp[k+1][len];
    memset(dp, 0, sizeof dp);

    for(int i=1;i<=k;++i) {
        int maxDiff=-prices[0];
        for(int j=1;j<len;++j) {
            dp[i][j]=max(maxDiff+prices[j], dp[i][j-1]);
            maxDiff=max(maxDiff, dp[i-1][j]-prices[j]);
        }
    }
    return dp[k][len-1];
}

int quickSolve(int k, vector<int>& prices) {
    int res = 0;
    for(int i=1;i<prices.size();++i) {
        int p = prices[i]-prices[i-1];
        if (p>0) res += p;
    }
    return res;
}

第五题

#面试 #DP

997. Find the Town Judge Combination Sum 系列