Algorithm
Problem Nmae: 121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int maxProfit(int* prices, int pricesSize) {
int i, d, k = 0;
if (pricesSize < 2) return 0;
// O(n)
int cost = prices[0];
for (i = 1; i < pricesSize; i ++) {
if (prices[i] > cost) {
d = prices[i] - cost;
k = d > k ? d : k;
} else {
cost = prices[i];
}
}
return k;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
vector<int>buy(prices.size());
vector<int>dp(prices.size());
buy[0] = prices[0];
dp[0] = 0;
for(int i = 1; i < prices.size(); i++){
buy[i] = min(buy[i - 1], prices[i]);
dp[i] = max(dp[i - 1], prices[i] - buy[i - 1]);
}
return dp[prices.size(> - 1];
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int maxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
}
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
}
Input
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const maxProfit = function(prices) {
let minPrice = Number.MAX_SAFE_INTEGER;
let maxP = 0;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxP) {
maxP = prices[i] - minPrice;
}
}
return maxP;
};
Input
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
diff_list=[0,0]
for i in range (1, len(prices)):
if prices[i]-prices[i-1]+diff_list[1]>=0:
diff_list[1]=prices[i]-prices[i-1]+diff_list[1]
diff_list[0]=max(diff_list[0],diff_list[1])
else:
diff_list[1]=0
return diff_list[0]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0121_BestTimeToBuyAndSellStock
{
public int MaxProfit(int[] prices)
{
int minPrice = int.MaxValue, maxProfit = 0;
for (int i = 0; i < prices.Length; i++)
{
if (prices[i] < minPrice) minPrice = prices[i];
else
maxProfit = Math.Max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
}
}
Input
Output