The title

LeetCode 121, Best time to buy and sell stocks Association type: Array dynamic programming

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, return 0. 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. Example 2: input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Time to solve the problem.

class Solution {
    public int maxProfit(int[] prices) {



    }
}
Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. Using a single cycle, the current NTH term minus the minimum of the first n minus 1 term is the maximum profit of the first n terms
  2. Define two values to record the minimum and maximum profit of the first n items respectively

Answers to analysis

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Answer successful: Execution time :3 ms, beat 56.51% of Java users memory consumption :51.5 MB, beat 41.40% of Java users

class Solution {
    public int maxProfit(int[] prices) {
        int maxVal = 0;
        int minNum = prices[0];
        for (int i = 0; i < prices.length;i++) {
            maxVal = Math.max(maxVal, prices[i] - minNum);
            minNum = Math.min(minNum, prices[i]);
        }
        return maxVal;
    }
}
Copy the code