Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades as possible (buying and selling a stock multiple times)

Leetcode-cn.com/problems/be…

Example 1:

Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can’t buy stocks on day 1 and day 2 and then sell them later. Because you’re doing multiple trades at once, you have to sell your shares before you can buy them again.

Example 3:

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

Tip:

1 <= prices.length <= 3 * 10 ^ 4 0 <= prices[i] <= 10 ^ 4

Java solution

Ideas:

  • In fact, yesterday’s solution to sell the way of processing changes, roughly the same
  • Here you need to capture every uptrend and sell when it goes down
package sj.shimmer.algorithm.m3_2021;

/** * Created by SJ on 2021/3/27. */

class D60 {
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[] {7.1.5.3.6.4}));
        System.out.println(maxProfit(new int[] {1.2.3.4.5}));
        System.out.println(maxProfit(new int[] {7.6.4.3.1}));
    }


    public static int maxProfit(int[] prices) {
        int result = 0;
        if(prices ! =null && prices.length > 1) {
            int length = prices.length;
            int in = 0;
            for (int i = 1; i < length; i++) {
                if (prices[i] < prices[i-1]) {
                    result+=prices[i-1]-prices[in];
                    in = i;
                }
            }
            result+=prices[length-1]-prices[in];
        }
        returnresult; }}Copy the code

The official solution

Leetcode-cn.com/problems/be…

  1. Dynamic programming

    The payoff on day I depends on whether it’s held on day I minus day 1, so write the dynamic equation and write the code

    class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0] [0] = 0;
        dp[0] [1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]);
        }
        return dp[n - 1] [0]; }}Copy the code

    It may seem a bit cumbersome, but it’s a good example of a dynamic programming solution

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

  2. greedy

    It’s similar to what I did, but I calculated the interval for each price, and I got rid of the negative numbers

    class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        returnans; }}Copy the code
    • Time complexity: O(n)
    • Space complexity: O(1)