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)