The best time to buy and sell stocks

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.

For details, see the LeetCode official website.

Source: LeetCode link: leetcode-cn.com/problems/be… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: dynamic programming

If prices is empty or there is only one value for prices, return 0.

Otherwise, declare a variable where result is 0 and buyPrice is the first value of prices, iterating from the second value of prices:

  • If the current value is equal to buyPrice, the next value is skipped;
  • If the current value is less than buyPrice, update buyPrice to the current value;
  • If the current value is greater than buyPrice, determine whether the difference between the current value and buyPrice is greater than that of result, and if so, update the value of Result.

When the traversal is complete, result is returned.

public class LeetCode_121 {
    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int result = 0;
        int buyPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] == buyPrice) {
                continue;
            } else if (prices[i] < buyPrice) {
                buyPrice = prices[i];
            } else {
                if(prices[i] - buyPrice > result) { result = prices[i] - buyPrice; }}}return result;
    }

    public static void main(String[] args) {
        int[] prices = new int[] {7.1.5.3.6.4}; System.out.println(maxProfit(prices)); }}Copy the code

March goes quietly, April comes lightly. April is the most beautiful day. The road ahead is open and everything is possible.