【LeetCode】4. Best time to buy and sell stock

Title Description

Description in English

You are given an array prices where prices[i] is the price of a given stock on the i(th) day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

English address

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Description of Chinese version

Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price . You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get . Return the maximum profit you can make from the deal . If you can't make any profit , return 0.

Example 1：

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

Output ：5

explain ： In the 2 God （ Stock price = 1） Buy when , In the 5 God （ Stock price = 6） Sell when , Maximum profit = 6-1 = 5 .

Note that profit cannot be 7-1 = 6, Because the selling price needs to be higher than the buying price ; meanwhile , You can't sell stocks before you buy them .

Example 2：

Input ：prices = [7,6,4,3,1]

Output ：0

explain ： under these circumstances , No deal is done , So the biggest profit is 0.

Constraints· Tips ：

• 1 <= prices.length <= 10(5)

• 0 <= prices[i] <= 10(4)

Address of Chinese version

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

Their thinking

You need to traverse the input array from scratch , Set two variables respectively （ Current minimum and current maximum ）, At the beginning, assign the first value of the array to two variables at the same time , Then start with the second , When a number smaller than the current minimum value is encountered, it will be re assigned to the current minimum value , If you encounter a number larger than the current maximum value, you will re assign it to the current maximum value , After the traversal is over , return （ Current maximum - Current minimum ） The difference between the . Take every value , Get the maximum difference between the value behind him and him , Go back to the biggest one

How to solve the problem

My version

class Solution {
     public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int minValue = prices[0];
        int step = 0;
        for (int i = 1; i < prices.length; i++) {
            int value = (prices[i] - minValue);
            if (value > 0) {
                if (step < value) {
                    step = value;
                }
            } else {
                minValue = prices[i];
            }
        }
        return step;
    }
}

Official edition

Dynamic programming

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

​ This is my closest official solution ～～ And the flower *･゜ﾟ･*:.｡..｡.:*･'(*ﾟ▽ﾟ*)'･*:.｡. .｡.:*･゜ﾟ･*