This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Suppose the price of a stock is stored in an array in chronological order. What is the maximum profit that can be made by trading the stock at one time?

Example 1: input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and 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 greater than the buying price. Source: LeetCode Link: https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Train of thought

• Buying and selling stocks is a kind of classic problem, we need to seriously analyze, find out the answer to the question.
• In view of this problem, it is analyzed that the first need is to find the minimum price, and then sell at a relatively high price, so as to obtain the maximum profit.

AC code

public class DayCode {
    public static void main(String[] args) {
        int[] prices = new int[] {7.1.5.3.6.4};
        int ans = new DayCode().maxProfit(prices);
        System.out.println(ans);
    }

    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                intprofit = prices[j] - prices[i]; maxProfit = Math.max(profit, maxProfit); }}return maxProfit;
    }

    public int maxProfit1(int[] prices) {
        int maxProfit = 0;
        int min = Integer.MAX_VALUE;
        for (int price : prices) {
            if (price < min) {
                min = price;
            } else if(price - min > maxProfit) { maxProfit = price - min; }}returnmaxProfit; }}Copy the code

Submit the test

conclusion

• Solution one is order n times n in time, order 1 in space.
• Solution two is order n in time, order 1 in space.
• Stick to the daily question, come on!