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, where prices[I] is the day I price of a given stock.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as you can.

Note: You cannot participate in more than one trade at a time (you must sell your shares before buying again).

Example 1: Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're on multiple trades at once, you have to sell your shares before buying again. Example 3: 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.

Profit [I][1] = math.max (profit[i-1][1], profit[i-1][0]-prices[I]); (You can buy shares more than once)

The best time to buy and sell stocks

Dynamic programming

Profiti is the maximum profit obtained on day I (j=0 is the maximum profit without the stock in hand, j=1 is the maximum profit with the stock in hand)

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] [0] = 0;
        profit[0] [1] = -prices[0];
        for(int i=1; i<prices.length; i++){
            profit[i][0] = Math.max(profit[i-1] [0], profit[i-1] [1]+prices[i]);
            profit[i][1] = Math.max(profit[i-1] [1], profit[i-1] [0]-prices[i]);
        }
        return profit[prices.length-1] [0]; }}Copy the code

To optimize the

The new state is only related to one neighboring state, which reduces the space complexity

class Solution {
    public int maxProfit(int[] prices) {
        int profit_0 = 0, profit_1 = -prices[0], profit_0_pre = 0;  Profit_0 = profit[i-1][0] profit_1 = profit[i-1][1]
        for(int i=1; i<prices.length; i++){
            profit_0 = Math.max(profit_0, profit_1+prices[i]);  / / profit_0_pre is to avoid the lost profit because of profit_0 update [0] [I - 1]
            profit_1 = Math.max(profit_1, profit_0_pre-prices[i]);
            profit_0_pre = profit_0;
        }
        returnprofit_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