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

The title

Given an array prices, where prices[I] is the day I price of a given stock.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as you can.

Note: You cannot participate in more than one trade at a time (you must sell your shares before buying again).

The sample

Input: prices = [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. Input: prices = [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 on multiple trades at once, you have to sell your shares before buying again. 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 <= 3 *
    1 0 4 10^4
  • 0 <= prices[i] <=
    1 0 4 10^4

Their thinking

121. What is the best time to buy or sell a stock? 121.

Then we can do expansion on the basis of the previous, statistical position and short position of the state, in each time there is a low when the buying operation, high sell, cumulative total earnings.

Code implementation

Method 1: dynamic programming

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        // 0 is a short position and 1 is a hold position
        dp[0] [0] = 0;
        dp[0] [1] = -prices[0];
        for(int i = 1; i < n; ++i){
            // The previous day's short position gains, open position profits
            dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i]);
            // The cost of the previous day's position, which lowers the cost of the position
            dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]);
        }
        // Final revenue
        return dp[n - 1] [0]; }}Copy the code

Complexity analysis

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

Way two: greed

We can assume a buy at every position and a sell at every high. Then we just need to determine that the price of the day was higher than the day before, and we can add up the difference between the two days.

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0, n = prices.length;
        for(int i = 1; i < n; ++i){
            // The current stock price is higher than the previous day
            if(prices[i] > prices[i - 1]) {// Add up the revenue
                res += prices[i] - prices[i - 1]; }}// Return the result
        returnres; }}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…