DP-State Machine

Question 1

121. Best Time to Buy and Sell Stock
     Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Answer 1

Code:-
You can always see the solution similar to the format below.

result = 0
min_value = prices[0]
for i in xrange(1, len(prices)):
result = max(result, prices[i] - min_value)
min_value = min(min_value, prices[i])
return result
But before that, take a look at the code below and see how it’s derived.

if(prices.length less than 1)
return 0;
int[] dp = new int[prices.length];
int minValue = prices[0];

for(int i=1; i less than prices.length; i++){
dp[i] = Math.max(dp[i-1], prices[i] - minValue);
minValue = Math.min(minValue, prices[i]);
}
return dp[prices.length-1];

There’s is a clear formula expression here, where dp[i] denotes the max profit on ith day.

We should get the max profit on (i + 1)th day from

profit from previous days, or
profit gained on this day (current price - minimum price before) And only after this, we can update the minimum price.

Then, according this ‘naive’ DP solution, we can see there’s only one variable needed for memorization. So we change the array dp[] to a variable, and thus change the space from O(n) to O(1).

(A good example of doing this reducing space would be knapsack problem. We can change the space complexity from O(mn) to O(n). I think you can discover that by yourself.)