This is the 14th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The title

Given an array prices, the i-th element prices[I] represents the i-th day price of a given stock.

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.

The sample

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1), 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; Also, you can't sell before you buy. 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

prompt

  • 1 <= prices.length <=
    1 0 5 10^5
  • 0 <= prices[i] <=
    1 0 4 10^4

Their thinking

This question is the easiest one in the series of forcingstocks, we just need to record each low price, and then keep updating its profit to get the final result.

Code implementation

Method one: dynamic programming

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length, min = prices[0];
        int[] dp = new int[n];
        
        for(int i = 1; i < n; ++i){
            // Update the lowest price
            if(min > prices[i]){
                min = prices[i];
            }
            // Update the maximum profit
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
        }
        
        // Return the result
        return dp[n - 1]; }}Copy the code

Complexity analysis

  • Time complexity: O(n)O(n)O(n).
  • Space complexity: O(n)O(n)O(n).

Method two: dynamic programming optimization

In method one, we only use the element dp[i-1], so we don’t need any of the previous elements anymore, so we can define a variable instead.

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length, max = 0, min = Integer.MAX_VALUE;

        for(int i = 0; i < n; ++i){
            // Update the lowest price
            if(min > prices[i]){
                min = prices[i];
            }
            // Update the maximum profit
            max = Math.max(max, prices[i] - min);
        }

        // Return the result
        returnmax; }}Copy the code

Complexity analysis

  • Time complexity: O(n)O(n)O(n).
  • Space complexity: O(1)O(1)O(1).

The last

The article has the bad place that writes, ask big guy people not stingy give instruction, mistake is most can let a person grow, wish I and big guy the distance between shorten gradually!

If you think the article is helpful to you, please like, collect, follow, comment one key four connect support, your support is my creation biggest power!!

Source: leetcode-cn.com/problems/be…