# Sharing my simple and clear C++ solution

• ``````int maxProfit(vector<int> &prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}
``````

minPrice is the minimum price from day 0 to day i. And maxPro is the maximum profit we can get from day 0 to day i.

How to get maxPro? Just get the larger one between current maxPro and prices[i] - minPrice.

• good I have the same idea

• I really love this solution: clear and short.

• my answer ,define more maxmum
int maxProfit(vector<int>& prices)
{
int iLength = prices.size();
int iMaxFit = 0, iMin = INT_MAX, iMax = INT_MAX;
for (int iIndex = 0; iIndex < iLength; iIndex++)
{
if (prices[iIndex] < iMin)
{
iMin = prices[iIndex];
iMax = iMin;
}
if (prices[iIndex] > iMax)
{
iMax = prices[iIndex];
if (iMax - iMin > iMaxFit)
{ iMaxFit = iMax - iMin; }
}
}
return iMaxFit;
}

• Very nice solution! But it still can be optimized. We only need to calculate either `maxProfit` or `minPrice` not both in every loop. Running time can be dropped by 33% percent.

``````public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) return 0;
int maxProfit = 0, minPrice = prices[0];

for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
} else {
minPrice = Math.min(minPrice, prices[i]);
}
}

return maxProfit;
}``````

• Don't down vote me. Haha. I've experimented and the time dramatically reduced.
We don't need to calculate max in every loop.

• If you use this method, take a look at Buy and Sell Stock III
similar solution: https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1

• I think comparing prices[i] and prices[i-1] also costs time.

• This post is deleted!

• making a graph describing price course based on day can help us understand it easly!

• I have implemented one place different by changing the order of updating the min-price and the max profit, then i GOT it wrong, I find the corner cases is important to deal with.

• Improve it more better

int maxProfit(int* prices, int pricesSize) {
if(!prices || pricesSize < 2) return 0;
int maxProfit = 0, minPrice = prices[0];

``````for(int i = 1; i < pricesSize; i++) {
if(prices[i] > minPrice) {
maxProfit = max(maxProfit, prices[i] - minPrice);
} else {
minPrice = min(minPrice, prices[i]);
}
}

return maxProfit;
``````

}

Very nice solution! But it still can be optimized. We only need to calculate either `maxProfit` or `minPrice` not both in every loop. Running time can be dropped by 33% percent.

``````public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) return 0;
int maxProfit = 0, minPrice = prices[0];

for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
} else {
minPrice = Math.min(minPrice, prices[i]);
}
}

return maxProfit;
}``````

• A little slow, but very clear and short after getting rid of the 'If'. Thanks for sharing!

• I think this is not the actual DP, Although I had the same idea.

• my version of solution, very similar idea

``````public class Solution {
public int maxProfit(int[] prices) {
if (prices == null) {
return 0;
}
int min = Integer.MAX_VALUE;
int profit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < min) {
min = prices[i];
} else {
profit = Math.max(profit, prices[i] - min);
}
}
return profit;
}
}
``````

• if(prices[i] > prices[i - 1]) {

However, instead of spending time calculate the MAX, you CPU needs more time checking whether prices[i] > prices[i - 1]). Thus, I don't think there will be much effect on run time.

• @zxyperfect Nice idea.

Python implementation

class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""

``````    profit = 0
min_price = 2**31

for x in prices:
min_price = min(min_price, x)
profit = max(profit, x-min_price)

return profit``````

• I use the same idea, but I use ternary operator instead of min and max function, that will be a little bit faster.

• The solution very clean and nice! The baisic idea is to continuously update minPrice and maxPro.

• clear and easy to understand

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.