This is the fifth day of my participation in the August Wen Challenge.More challenges in August

Topic describes

Given an array prices, its ith element prices[I] represents the price of a given stock on day I. You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make. Return the maximum profit you can make from the transaction. If you can't make any profit, return0. The sample1: Input: [7.1.5.3.6.4] output:5Explanation: In no2Day (stock price =1) time to buy, at No5Day (stock price =6), maximum profit =6-1 = 5. Notice the profit can't be7-1 = 6Because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them. The sample2: Input: prices = [7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0. Tip:1 <= prices.length <= 105
0 <= prices[i] <= 104Source: LeetCode//leetcode-cn.com/problems/best-time-to-buy-and-sell-stockCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. Violent solution

The solution to this problem is similar to Q217, which is to subtract the first element from all the other elements, and then get the maximum of all the results

public int maxProfit2(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            int compute = prices[j] - prices[i];
            if(compute > maxProfit) { maxProfit = compute; }}}return maxProfit;
}
Copy the code

Time is O(n^2), time out

2. The greedy

The so-called greed is to seek the local optimal solution every time, and finally get the overall optimal solution. However, not every time we get the local optimal solution, we will finally get the overall optimal solution, which leads to a concept: no aftereffect.

No aftereffect means that previous actions do not affect subsequent actions.

For an example of no backeffect, look at this article, which is very graphic: No backeffect, chess example

If we look at this problem again, the previous price of the stock doesn’t affect the current price, so it satisfies no aftereffect.

The local problem is to find the maximum profit value for the day

Answer:

  • Define two variables: minimum stock price and maximum profit
  • Through the array
  • If the current price is less than the minimum price, make the minimum price equal to the current price
  • If the current price minus the minimum price is greater than the maximum profit, let the maximum profit be equal to the current price minus the minimum price
public int maxProfit3(int[] prices) {
    int min = prices[0];
    int maxProfit = 0;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        }
        if(maxProfit < prices[i] - min) { maxProfit = prices[i] -min; }}return maxProfit;
}
Copy the code