• 40.0%

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

1. 寻找低谷与峰值之间的差。设置一个变量为低谷，vally，另一个变量为目前找到的最大值，maxsofar，则从头开始遍历，如果当前值小于vally，则此值与vally的差为负，所以vally改为当前值，如果当前值大于vally，则计算当前值与vally的差。一次遍历。
2. 第二种思路，重新设置一个数组，记录邻近两个数字的差，类似于寻找最长的数组。

Oct 17， 2017

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution

Sharing my simple and clear C++ solution

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.

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution/5

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.

#### cpp

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution

Sharing my simple and clear C++ solution

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.

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution/5

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.

https://discuss.leetcode.com/topic/42716/5-line-cpp-solution

5 line CPP solution

#### python

https://discuss.leetcode.com/topic/33241/easy-o-n-python-solution

Easy O(n) Python solution

#### java

Algorithm

Say the given array is:

[7, 1, 5, 3, 6, 4]

If we plot the numbers of the given array on a graph, we get:

The points of interest are the peaks and valleys in the given graph. We need to find the largest peak following the smallest valley. We can maintain two variables - minprice and maxprofit corresponding to the smallest valley and maximum profit (maximum difference between selling price and minprice) obtained so far respectively.

Complexity Analysis

• Time complexity : O(n)O(n). Only a single pass is needed.

• Space complexity : O(1)O(1). Only two variables are used.

my code:

The logic to solve this problem is same as “max subarray problem” using Kadane’s Algorithm. Since no body has mentioned this so far, I thought it’s a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

• maxCur = current maximum value

• maxSoFar = maximum value found so far