I punch simple algorithm questions | leetcode. [121] the best time to buy stocks – JAVA

This is the third day of my participation in Gwen Challenge

The original problem

The best time to buy and sell stocks

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

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.

• 
  $1 <= prices.length <= 10^5$
• 
  $0 <= prices[i] <= 10^4$

Example 1:

Input:7.1.5.3.6.4] output:5Explanation: In no2Day (stock price =1) time to buy, at No5Day (stock price =6), maximum profit =6-1 = 5. Notice the profit can't be7-1 = 6Because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Enter: prices = [7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

jolt

This is still labeled dynamic programming, so we’re going to follow the basics.

First carefully looked at the topic, the key is to buy low and sell high, so this topic must be sequential traversal, and the most bottom line is not to lose money, that is, do not buy stocks (indeed, do not buy stocks I will always earn).

• The boundary conditions

  So if they say prices.length>=1 then there’s no special boundary here, just remember the first value prices[I] is used to calculate.

  
  $$dp(n)=\left\{ \begin{aligned} prices[0] & &\ n = 1 \\ ??? & & \ n > 1 \\ \end{aligned} \right.$$

• subproblems

  Prices is an array of length I, so if you want to buy low and sell high, you’re looking at the order of the array and you’re looking for the biggest difference. One condition, of course, is that the result must be greater than zero.

  This wave sets the subproblem to the maximum value of low buy and high sell when the array length is N

  Then the human brain calculates that this is an array of length N (0 < n << I). First, it needs to find the lowest buying point from front to back, that is, the minimum buying value, which can be retained by using a parameter min. So, if the current dp[n] array earns the most is RES, then the lowest buy point is min. When it extrapolates down, the array becomes length n + 1, the res value is associated with the NTH element of the array, which is used to subtract the previous minimum purchase point and compare it with the existing value, and the replacement of the minimum purchase point is also continued. In this way, there are two results:

  1. You make more money at length n, and you go down to the NTH element

  2. Sell at the NTH element, make more money than before, record dp[n], and keep going

  This is the one that you can compute all the way down to n is equal to I. You just have to finally iterate dp[n] to find the maximum

• equation

  According to the previous item, it can be obtained as follows:

  
  $$dp(n)=\left\{ \begin{aligned} prices[0] & &\ n = 1 \\ Max(dp[n], prices[n] – min) & & \ n > 1 \\ \end{aligned} \right.$$

  When the array prices[I] is traversed, the result is a dp[n] array with length N, the maximum amount of money that can be made by selling high and buying low.

• Write code that combines conditions

    public int maxProfit(int[] prices) {
        // The boundary conditions of the problem
        if (prices.length == 1) {
            return 0;
        }
        // Min buy point comparison, remember to initialize the theoretical maximum
        int min = Integer.MAX_VALUE;
        int[] dp = new int[prices.length+1];
        / / initial value
        dp[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            // Cycle the lowest buy point you can find
            min = Math.min(min, prices[i-1]);
            // The difference is bigger than that
            dp[i] = Math.max(dp[i], prices[i] - min);
        }
        // The minimum value is Integer.MIN_VALUE
        int res = 0;
        // find the most profitable case
        for (int i : dp) {
            if(res < i){ res = i; }}return res;
    }
Copy the code

It then runs and finds that execution time beats 19.44% and memory beats 6.19%

This situation can be spatially optimized, because you just need to iterate while maximizing the error.

Changed:

    public int maxProfit(int[] prices) {
        if (prices.length == 1) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int dp = 0;
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i-1]);
            dp = Math.max(dp, prices[i] - min);
            if(dp > res) { res = dp; }}return res;
    }
Copy the code

It then ran and found that the execution time beat 60.90% and memory beat 56.83%

The effect is ok, and then down, temporarily did not think, in the future, after all, I can only simple skills.

closed

• Spatial optimization of dynamic programming is necessary