Subject to introduce

Force buckle 121 questions: leetcode-cn.com/problems/be…

Analysis of the

Computers solve problems by brute force. When confronted with a problem and unable to think of any clever tricks, ask the reader first how to enumerate all the possibilities of the problem.

The solution to this problem is simple, we can write code like this:

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int buy = 0; buy < prices.length; buy++) {
            for(int sell = buy + 1; sell < prices.length; sell++) { max = Math.max(max, prices[sell] - prices[buy]); }}returnmax; }}Copy the code

In fact, this solution is feasible and gives the correct answer, but the force connection times out. If we look at what this algorithm is doing, we can find some redundancy.

As shown in the figure above, you can see a lot of duplication. Prices [sell] — prices[buy] prices[sell] — prices[buy] prices[sell] — prices[buy] — prices[buy] — prices[sell] — prices[buy] — prices[sell] — prices[buy] — prices[sell] — prices[buy]

If prices were reversed, wouldn’t the same effect be achieved by fixing the time at which they sell and moving forward to buy at the lowest prices? Yes, and this way of thinking reduces a for loop.

public class Solution {
    public int maxProfit(int prices[]) {
        int res = 0;
        int curMin = prices[0];
        for (int sell = 1; sell < prices.length; sell++) {
            curMin = Math.min(curMin, prices[sell]);
            res = Math.max(res, prices[sell] - curMin);
        }
        returnres; }}Copy the code

Why can we reduce a for loop? Let me give you an example that will make it easier for you to understand.

Suppose you have a bunch of numbers, and you know the largest number, and now you take one of them, do you know what the largest number is? Not necessarily. If you take away something that’s not the largest number, then the largest number stays the same; If you take away the largest number, you have to go through the pile again to find the second largest number, which is the new largest number. So that’s our original algorithm, and every time we move back one bit, we’re going to iterate to find the maximum.

But, assuming you know the smallest number in a bunch, add a new number, do you now know what the smallest number is? Yes, just compare the new number to the current smallest number, you can get the new minimum number. This is the case with the optimization algorithm, so you can eliminate computational redundancy for nested loops.

It’s not about maximums or minimums, it’s about adding and subtracting numbers. When adding a new number, the new maximum value can be derived from the existing maximum value. And when reducing the number, not necessarily can directly derive the new maximum value, have to iterate.