A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

1. Topic description

Given an array prices, the i-th element prices[I] represents the i-th day price of a given stock.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Example 1: input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1), sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price; Also, you can't sell before you buy. Example 2: input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

2.

Dynamic programming

Profit [I][j] = maximum profit on day I (j=0 = maximum profit without stock, j=1 = maximum profit with stock)

There are two possibilities for me to own no stock today: either I didn’t own it yesterday, and I chose REST today, so I still don’t own it today; Either I owned the stock yesterday, but I sold today, so I don’t own the stock today.

I own the stock today, and there are two possibilities: EITHER I owned the stock yesterday and chose REST today, so I still own the stock today; Either I didn’t own it yesterday, but I bought it today, so I own the stock today.

In all cases, the maximum profit is at profit[prices.length-1][0], because profit is Max all the time, and the profit without stocks (j=0) is higher than that with stocks (j=1).

class Solution { public int maxProfit(int[] prices) { int profit[][] = new int[prices.length][2]; profit[0][1] = -prices[0]; profit[0][0] = 0; for(int i=1; i<prices.length; i++){ profit[i][1] = Math.max(profit[i-1][1], -prices[i]); profit[i][0] = Math.max(profit[i-1][0], profit[i-1][1]+prices[i]); } return profit[prices.length-1][0]; }}Copy the code

To optimize the

Profit_1 is profit[i-1][1], profit_0 is profit[i-1][0]

class Solution { public int maxProfit(int[] prices) { int profit_0 = 0, profit_1 = -prices[0]; for(int i=0; i<prices.length; i++){ profit_1 = Math.max(profit_1, -prices[i]); profit_0 = Math.max(profit_0, profit_1+prices[i]); } return profit_0; }}Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast