Buying and selling stocks is a more interesting problem, and the practical problems of life more relevant. The principle of buying at a low price and selling at a high price is to make profits. This topic mainly studies the maximum profit obtained from a single transaction within a certain period of time. (Beginners might do this.)

121 The best time to Buy and sell stocks (LeetCode)

The title

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 one stock), design an algorithm to calculate the maximum profit you can make. Note that you can't sell a stock before you buy it.Copy the code

Example 1:

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.Copy the code

Example 2:

Input:7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

Answer key:

  • Min_price [I] = math.min (min_price[i-1],nums[I]); Max_profile [I] = math.max (max_profile[i-1],nums[I]-min_price[i-1]); , and then go through it, constantly adjusting the minimum price and maximum profit.

The code is as follows:

package com.zhoujian.solutions.didi;
import java.util.Scanner;
/ * * *@author [email protected] 2018/9/8 15:39
 */
public class Stock1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] split = line.split(",");
        int n = split.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }
        int max_profit = maxProfit(nums,n);
        System.out.println(max_profit);
    }

    private static int maxProfit(int[] nums, int n) {
        if (nums == null || nums.length ==0) {
            return 0;
        }
        // Store the minimum price
        int[] min_price = new int[n];
        // Used to store maximum profits
        int[] max_profit = new int[n];
        // Define the minimum price for the first day
        min_price[0] = nums[0];
        max_profit[0] = 0;
        // Start traversing from the next day
        for (int i = 1; i < n; i++) {
            // Find the minimum value in the min_profile array
            min_price[i] = Math.min(min_price[i-1],nums[i]);
            // find the maximum value in max_profile,nums[I]-min_price[i-1] is the I value minus the minimum value in the previous sequence
            max_profit[i] = Math.max(max_profit[i-1],nums[i]-min_price[i-1]);
        }
        // Returns the maximum profit for the previous n-1 day
        return max_profit[n-1]; }}Copy the code

The results are as follows:

  • The time complexity is O(n), and the space complexity is O(n).