Xiaobai learning algorithm: the best time to buy and sell stocks!

Today, the ant group (Alipay) is officially listed. There is no doubt that this initiative has created a large number of rich people. However, as an outsider, we have only envy. Obviously, we can take a chance to eat.

But then again, the people who can enter ants are also cattle. Let's improve our skills quickly so as to make full preparations for the next "ant".

Today's question is more interesting. It's about "buying and selling stocks". The questions are as follows.

Title Description

Given an array, its i-th element is the price of a given stock on day I. If you are allowed to complete only one transaction at most (i.e. buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

Example 1:

Example 2:

Problem solving ideas

According to the meaning of the title, we know that we only have one trading opportunity, that is, buy and sell again, but at the same time, we should ensure the maximization of income. Our instinct is to buy at the lowest price and then sell at the highest price, as shown in the figure below:

But there is a problem, that is, we should ensure that the highest price is after the lowest price, because we must buy stocks before we can sell them, not in the opposite order, which makes the problem more complicated.

But now we think of the most direct and stupid method, that is, the violent exhaustive method. We use a two-tier cycle, buy at each node in turn, and then sell at all subsequent nodes, In this way, the difference (revenue) between nodes is calculated. If the difference is greater than the current maximum revenue, set this value to the current maximum revenue. After the cycle is completed, we can obtain the maximum revenue, as shown in the figure below:

Method 1: Violence Law

With the above ideas, let's implement it in Code:

class Solution {
    public int maxProfit(int[] prices) {
        int mp = 0; // 最高收益
        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;
            }
        }
        return mp;
    }
}

We can see that the code is still very simple, but don't be happy too early. Let's look at its performance on leetcode:

Complexity analysis

What a meal, the operation was as fierce as a tiger, and finally defeated 5%! If you use this code to interview, you may have to go back and wait for the notice. Is there a better way? The answer is yes. Keep looking.

Method 2: traverse once

We can actually use one cycle to solve this problem. Let's take a look at the following line chart:

From the above picture, we can see that we can only do two things at each node (except the first node, which can only buy but not sell). The two things are: buy or sell. Then we can actually use a cycle to calculate the maximum profit. We only need to make the following two judgments for each node in turn:

In this way, after the cycle is completed, the maximum income will be obtained. The implementation code is as follows:

class Solution {
    public int maxProfit(int prices[]) {
        if (prices == null || prices.length == 0) return 0;
        int mp = 0; // 最高收益
        int min = prices[0]; // 最低价
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                // 设定相对最低价
                min = prices[i];
            } else if (mp < (prices[i] - min)) {
                // 设定最高盈利
                mp = prices[i] - min;
            }
        }
        return mp;
    }
}

The results of the above codes in leetcode are shown in the following figure:

Complexity analysis

From the above execution results, we can see that this code is ideal, so that the interviewer will give you a thumbs up.