Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/122.html

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

Constraints:

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

Algorithm

Starting from the second day, if the current price is higher than the previous day’s price, we can add the difference to the profit because we can buy the stock on the previous day and sell it today at a higher price. Similarly, if the price is even higher on the following day, we can buy the stock today and sell it again tomorrow at an even higher price. By repeating this process for the entire array of stock prices, we can obtain the maximum possible profit.

Code

  • 
public class Best_Time_to_Buy_and_Sell_Stock_II {


    class Solution {
        public int maxProfit(int[] prices) {

            if (prices == null || prices.length == 0) {
                return 0;
            }
            int result = 0;

            for (int i = 1; i < prices.length; i++) {
                int singleDayProfit = prices[i] - prices[i - 1];
                if (singleDayProfit > 0) {
                    result += singleDayProfit;
                }
            }

            return result;
        }
    }
}

############

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for (int i = 1; i < prices.size(); ++i) ans += max(prices[i] - prices[i - 1], 0);
        return ans;
    }
};

  • '''
>>> from itertools import pairwise
>>> dirs = (-1, 0, 1, 0, -1)
>>> pairwise(dirs)
<itertools.pairwise object at 0x104dbe470>
>>> list(pairwise(dirs))
[(-1, 0), (0, 1), (1, 0), (0, -1)]
'''

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(max(0, b - a) for a, b in pairwise(prices))


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum( max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)) )


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum( prices[i] - prices[i - 1] for i in range(1, len(prices)) if prices[i] > prices[i - 1] )

############

class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    ans = 0
    for i in range(1, len(prices)):
      if prices[i] > prices[i - 1]:
        ans += prices[i] - prices[i - 1]
    return ans


  • func maxProfit(prices []int) (ans int) {
	for i, v := range prices[1:] {
		t := v - prices[i]
		if t > 0 {
			ans += t
		}
	}
	return
}

  • function maxProfit(prices: number[]): number {
    let ans = 0;
    for (let i = 1; i < prices.length; i++) {
        ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
}


  • /**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let ans = 0;
    for (let i = 1; i < prices.length; i++) {
        ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
};


  • public class Solution {
    public int MaxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.Length; ++i) {
            ans += Math.Max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

  • impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut res = 0;
        for i in 1..prices.len() {
            res += 0.max(prices[i] - prices[i - 1]);
        }
        res
    }
}

All Problems

All Solutions