Stock Trading Problems: From One Deal to K Deals

One transaction only. Find max profit?

This works like the maximum subarray sum problem. The difference is that subarrays depend on current elements versus current plus previous sum. Stock prices depend on the max right value minus min left value in increasing subsequences. We can still use continuous thinking here. If the subarray increases, we just sum up differences between adjacent elements. This equals the profit from one buy-sell pair. Here we use DP thinking. If the subarray decreases somewhere, we should start accumulating from smaller values to get global optimal profit. The accumulation sum should reset to 0 and start over. Take the maximum throughout the process.

// Maximum subarray sum
// 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;
}

A small change gives us the solution:

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;
}

Second Problem

Unlimited transactions. Find max profit?

No limits means we can use greedy approach. Just take any profit when it exists.

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;
}

Third Problem

At most 2 transactions. Still find max profit?

Think like a gambler. Say we made $10 on our first trade. We won’t walk away yet. If the stock price is $10, we’ll buy again. Maybe we can make more next time? Based on this multi-stage greedy thinking, we solve it by putting all hope on the final selling profit.

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;
}

Or we can use regular 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];
}

Fourth Problem

Trade up to K times. Watch the range of K. If K x 2 exceeds price length, we can solve greedily. Otherwise use the same DP equation as problem three, extract common factors to reduce computation. Here’s the solution:

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;
}

Fifth Problem

#interview #DP

Squares of a Sorted Array Stone Game