## Best Time to Buy and Sell Stock III

07/11/2016 Array Dynamic Programming

## Question

Say you have an array for which the $i^{th}$ element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

## Solution

Result: Accepted Time: 4 ms

Here should be some explanations.

int imax(int a, int b){ return a > b ? a : b; }

int maxProfit(int* prices, int psz)
{
// 0 one buy 1 one sell 2 two buy 3 tow sell
int dp={-prices, 0, INT_MIN ,0}, now = 1, last = 0;
for(int i = 1; i < psz; i++)
{
dp[now] = imax(dp[last], -prices[i] );
dp[now] = imax(dp[last], dp[last] + prices[i]);
dp[now] = imax(dp[last], dp[last] - prices[i]);
dp[now] = imax(dp[last], dp[last] + prices[i]);
last = now;
now ^= 1;
}
return imax(dp[!(psz&1)],dp[!(psz&1)]);
}


Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$