The title information

Subject address: leetcode-cn.com/problems/be…

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.

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:

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

Tip:

1 <= prices.length <= 105
0 <= prices[i] <= 104
Copy the code

Solution 1: violent solution

The violent solution should be the solution that everyone thinks of when they see the problem, and here is no exception. Let’s write a violent solution. So you take all the combinations and you maximize the payoff

For example: [7,1,5,3,6,4]

7 -> 1 = -6
7 -> 5 = -2
7 -> 3 = -4
7 -> 6 = -1
7 -> 4 = -3
1 -> 5 = +4
1 -> 3 = +2
1 -> 6 = +5
1 -> 4 = +3
5 -> 3 = -2
5 -> 6 = +1
5 -> 4 = -1
3 -> 6 = +3
3 -> 4 = +1
6 -> 4 = -2
Copy the code

After exhausting all the buy and sell combinations, the maximum return is +5

Implementation steps:

The first is to scan all the combinations

The second is to record Max

Third returns the final Max

The code is as follows:

public int maxProfit(int prices[]) {
    int max = 0;
    for(int i = 0; i < prices.length-1; i++){
        for(int j = i+1; j < prices.length; j++){
            int income = prices[j] - prices[i];
            if(income > max){ max = income; }}}return max;
}
Copy the code

The outer cycle is n-1 times, and the inner cycle is (n-1, n-2,…. 1) Total n22\frac{n^2}{2}2n2 time complexity is O(n^2)

The space only uses two variables so it’s O(1).

Solution two: dynamic programming

The time complexity of the previous solution was too high, and the LeetCode tests also timed out. As a dynamic programming set of problems we’re definitely going to use dynamic programming to solve a problem.

How do we think about:

How can the ultimate maximum return of day I be divided?

  1. It could be that the maximum return on the previous i-1 day is the same
[4.2.1.5.4] this5Day maximum return is the third day to buy the fourth day to sell the highest4Is the former4The highest combination of days.Copy the code
  1. It may also vary more than the previous i-1 day’s maximum return
[4.2.1.5.7] this5Before the days of4Day maximum yield is4In the first5Oh, god, it should be6
Copy the code

So here we can see that it maximizes in one of two ways

Maximum return on day 1 = Max (maximum return on day 1 before i-1, price on day I - minimum price on day 1 before I-1)

I’m going to iterate over and store not only the payoff but also the minimum so it’s better to go from the bottom up. Check if Max is the same or larger after each iteration (record the current minimum and the current result)

The code is as follows:

public int maxProfit(int[] prices) {
    if(prices.length < 2) {return 0;
    }
    int min = prices[0];
    int max = 0;
    for(int i = 1; i < prices.length; i++) {
        max = max > (prices[i] - min) ? max : prices[i] - min;
        min = min < prices[i] ? min : prices[i];
    }
    return max;
}
Copy the code

Top down is a little bit more troublesome than bottom up. But the idea is the same. Let me draw a picture here

The code is as follows:

public int maxProfit(int[] prices) {
    return recurrent(prices,prices.length-1);
}
int recurrent(int[] nums,int index){
    if(index == 0) {return 0;
    }
    int right = nums[index] - min(nums,index);
    int left = recurrent(nums,--index);
    if(left > right){
        return left;
    }
    return right;
}
int min(int[] nums,int index){
    int min = nums[0];
    for(int i = 1; i < index; i++){
        if(nums[i] < min){ min = nums[i]; }}return min;
}
Copy the code

It has an iterative depth of n, but it has a minimum of n next to it, so the time complexity is O(n2n^2n2), and if it’s recursive it’s almost O(2n2^n2n). But even n to the second power is as complex as timeout and violence.

After all, the idea of only iterating is not documented. And on this side, because the recursive part is linear, there’s nothing extra, but basically the minimum side is going to average n over 2 times each. So it’s ok to record if the current index is not the previous minimum. It means that the minimum value of the rest of the sequence is still in there and you don’t have to iterate over it. The overall complexity is still not good.

conclusion

Today’s problem is easier to do, but the difference is that the structure of the iteration is not the same type. Dynamic programming problems can be practiced simultaneously in both top-down and bottom-up directions.