This article has been included in Github “Xiaobai Algorithms” series: github.com/vipstone/al…

Today ant Group (Alipay) officially listed, there is no doubt that this move has created a large number of rich people, but as outsiders, we can only envy. Obviously can test luck to eat, we have to rely on strength, you say injustice ah?

On the other hand, anyone who can get into ants is a great person, so let’s upgrade our skills so we can prepare for the next ant.

Buy and sell stocks.

Topic describes

Given an array, its ith element is the price of a given stock on the ith day. If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

Note: You cannot sell a stock before you buy it.

Example 1:

Input:,1,5,3,6,4 [7]

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 higher than the buying price; Also, you can’t sell stocks before you buy them.

Example 2:

Input:,6,4,3,1 [7]

Output: 0

Explanation: In this case, no transaction is completed, so the maximum profit is 0.

Source: LeetCode

Offer 64: leetcode-cn.com/problems/gu… The difficulty:

Leetcode 121:leetcode-cn.com/problems/be… Difficulty: Easy

Their thinking

We have only one chance to buy and sell again, but at the same time we need to maximize the profit. Our instinctive instinct is to buy at the lowest price and sell at the highest, as shown below:

But one problem is that we have to make sure that the highest price is after the lowest price, because we have to buy the stock before we can sell it, not the other way around, which makes things complicated.

But at the moment we came up with a most direct and the most stupid one method, that is to use violence exhaustive method, we use two layers of circulation, on each node in order to buy, then after sell all nodes, so that to calculate the difference in value between nodes (earnings), if the difference is greater than the current highest yield, and value will be set to the current highest yield, finish this cycle, We’ll get the most out of it. As shown below:

Method one: violence method

With the above idea, let’s use the code to implement:

class Solution {
    public int maxProfit(int[] prices) {
        int mp = 0; // Maximum revenue
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int item = prices[j] - prices[i];
                if(item > mp) mp = item; }}returnmp; }}Copy the code

As you can see, the code is still pretty simple, but don’t get too excited, let’s see how it looks on LeetCode:

Complexity analysis

  • Time complexity: O(n^2), run n(n-1)/2 times.
  • Spatial complexity: O(1), only constant digit variables are used.

That was one hell of a operation, beating five percent! If you use this code for an interview, you’ll probably have to go back and wait for a call. Is there a better way? The answer is yes, keep reading.

Method 2: Iterate once

We can actually use a loop to do this. Let’s look at the line graph below:

As we can see from the picture above, we actually do two things at each node (except for the first node, which can only be bought but not sold) : buy or sell. So we can actually use a cycle to calculate the maximum profit, we just need to make the following two judgments for each node in turn:

  • Determine if the current node is relatively low and if so, set it to low (i.e., buy);
  • If the current node is not the lowest, we sell it and calculate the gain from selling (the current node minus the relative low price). If the gain from selling is greater than the current maximum gain, we set this value to the highest gain.

When the loop is complete, the highest return comes out. The code is as follows:

class Solution {
    public int maxProfit(int prices[]) {
        if (prices == null || prices.length == 0) return 0;
        int mp = 0; // Maximum revenue
        int min = prices[0]; / / the lowest price
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                // Set a relative minimum price
                min = prices[i];
            } else if (mp < (prices[i] - min)) {
                // Set maximum profitmp = prices[i] - min; }}returnmp; }}Copy the code

The result of the above code in LeetCode is shown below:

Complexity analysis

  • Time complexity: O(n), only need to traverse once.
  • Space complexity: O(1), using only constant variables.

From the results of the above implementation, this code is relatively ideal, so that the interviewer will give you a thumbs up.

conclusion

In this paper, we calculated the maximum return of a single stock (a buy and sell). At the beginning, we used the simplest and crude violence enumeration method, which used two cycles of subtraction to find the maximum return value, but the execution efficiency of this method was too low.

Then we looked at the line chart and found that it only took one cycle to find the highest return value. We only need to make two judgments on each node. First, judge whether this node is a relatively minimum value, and if so, record it. If not, calculate whether this value and the relative minimum are the current highest returns, and if so, record them. Then after the loop, we can get the highest return and execute efficiently.

Did you learn? If you have any questions or better methods, please leave a comment in the comments section

Bonus: search the public account “Java Chinese Community” and send “interview” to receive the latest interview materials.