For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: The best time to buy and sell stocks

Title source: leetcode-cn.com/problems/be…

Given an array, its ith element is the price of a given stock on the ith day.

If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

Note: You cannot sell a stock before you buy it.

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 higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

The problem solving scheme

This problem with violence to do the answer is relatively simple, is the time-consuming violence more touching.

We loop through the outermost loop, loop through the array, and then loop through the inner loop, differentiate each of the outermost loops, save the largest difference, and return the largest difference that we just evaluated.

public int maxProfit(int[] prices) {
     int maxProfit = 0;
     for (int i = 0; i < prices.length; i++) {
          for (intj = i; j < prices.length; j++) { maxProfit = Math.max(maxProfit, prices[j] - prices[i]); }}return maxProfit;
}
Copy the code

This code is absolutely simple, it reminds me of bubble sort…

Then I ran the code in LeetCode, and it took me an astronomical amount of time…

What did I do? It was a simple double cycle. How did I spend my time?

Well, go ahead and look at the answer, which offers a way to loop the answer just once.

But this is a very poor explanation of the solution, and it has to be applied to the scene.

No need at all, first look at the code, the code is relatively simple, read all understand:

public int maxProfit_1(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;
}
Copy the code

My understanding of this code is that in the process of the loop, I look for the smallest value minPrice, because the selling price must be behind the buying price, so I always subtract the smallest value minPrice from the current value in the loop, so as to get the value of Maxprofit.