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.
Example
Given array [3,2,3,1,2], return 1.
A smart way is to record the minimum buy-in price before dayi , and the maximum profit by selling the stock on day i would be their difference.
遍历数组，并且维护一个最小股价和一个最大利润。
如果当前股价 - 最小股价 > 最大利润，那么我们更新最大利润。
最小股价为当前股价和之前最小股价的较小值。
public int maxProfit(int[] prices) { if(prices==null||prices.length<=1){ return 0; } int min=prices[0]; int profit=0; for(int i=1;i<prices.length;i++){ min = Math.min(min,prices[i]); profit = Math.max(profit, prices[i]-min); } return profit; }
X.
Related:http://www.geeksforgeeks.org/maximum-difference-between-two-elements/
First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.
We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop.
Brute Force:
http://blog.csdn.net/u014688145/article/details/70992371
它的每一个历史最低点都会向后找【所有】历史最高点去比较（你也可以看作是跟每个向后的历史值去比较，只要维护一个maxProfit即可），所以它可以逆向思考，也就是说，遍历到当前点，我们可以向前去比较历史最低点，不断更新
但需要明确一点，之所以可以这样做，无非两点，之前的信息我们可记录（维护一个最小的
public int maxProfit(int[] prices) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int i =0;i<prices.length;i++){ if (prices[i] < minprice){ minprice = prices[i]; }else if (prices[i]-minprice > maxprofit){ maxprofit = prices[i] - minprice; } } return maxprofit; }
这是一种思路，带来了O(n) 的解决方案。再来看一种解决方案，核心思想如下：
1. 卖的同时可以瞬间买进。（多个操作可以看成一个操作）
2. 没钱的情况下，可以看作向别人借钱（记忆）
虽然代码形式和上一种不太一样，但它们本质上是一种形式，可以互相转换。但该代码的好处在于它更加亲民接地气。更符合人的认知，buy可以看作是借钱的过程，而
public int maxProfit(int[] prices) { int buy = Integer.MIN_VALUE; int sell = 0; for (int price : prices){ buy = Math.max(buy, -price); sell = Math.max(sell, buy + price); } return sell; }
它还有另外一种解法，它的买卖同时更加形象。利用的是势能不断增加，突破max就更新max，当价格下降时，势能降低，但最低不超过0。（sum减到0就停止更新）
就从整个prices的价格走势来看，只要有上升的情况，我们就可以使用
public int maxProfit(int[] prices) { int sum = 0; int max = 0; for (int i = 1; i < prices.length;i++){ sum = Math.max(0, sum += prices[i]-prices[i-1]); max = Math.max(max, sum); } return max; }
Read full article from LeetCode - Best Time to Buy and Sell Stock | Darren's Blog
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.
Example
Given array [3,2,3,1,2], return 1.
A smart way is to record the minimum buy-in price before day
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0)
return 0;
int lowestBuyInPrice = prices[0]; // Lowest buy-in price up to now
int maximumProfit = 0; // Maximum profit up to now
for (int i = 1; i < prices.length; i++) {
// Update the maximum profit if buying the stock with the lowest price up to now and
// selling it in day i makes greater profit
maximumProfit = Math.max(maximumProfit, prices[i]-lowestBuyInPrice);
// Update the lowest price if the price in day i is smaller than those in earlier days
lowestBuyInPrice = Math.min(lowestBuyInPrice, prices[i]);
}
return maximumProfit;
}
https://xuezhashuati.blogspot.com/2017/04/lintcode-149-best-time-to-buy-and-sell.html遍历数组，并且维护一个最小股价和一个最大利润。
如果当前股价 - 最小股价 > 最大利润，那么我们更新最大利润。
最小股价为当前股价和之前最小股价的较小值。
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int minPrice = Integer.MAX_VALUE; int maxProfit = Integer.MIN_VALUE; for (int i = 0; i < prices.length; i++) { int currPrice = prices[i]; int currProfit = currPrice - minPrice; minPrice = Math.min(minPrice, currPrice); maxProfit = Math.max(maxProfit, currPrice - minPrice); } return maxProfit; }https://leetcode.com/discuss/9212/a-o-1-n-solution
public int maxProfit(int[] prices) { if(prices==null||prices.length<=1){ return 0; } int min=prices[0]; int profit=0; for(int i=1;i<prices.length;i++){ min = Math.min(min,prices[i]); profit = Math.max(profit, prices[i]-min); } return profit; }
X.
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. public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}
*
maxCur = current maximum value
*
maxSoFar = maximum value found so far
Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].
Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)
In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far (max_diff).
2) Minimum number visited so far (min_element).
1) Maximum difference found so far (max_diff).
2) Minimum number visited so far (min_element).
int maxDiff(int arr[], int arr_size){ int max_diff = arr[1] - arr[0]; int min_element = arr[0]; int i; for(i = 1; i < arr_size; i++) { if (arr[i] - min_element > max_diff) max_diff = arr[i] - min_element; if (arr[i] < min_element) min_element = arr[i]; } return max_diff;}
Like min element, we can also keep track of max element from right side. See below code suggested by Katamaran
int maxDiff(int arr[], int n){ int maxDiff = -1; // Initialize Result int maxRight = arr[n-1]; // Initialize max element from right side for (int i = n-2; i >= 0; i--) { if (arr[i] > maxRight) maxRight = arr[i]; else { int diff = maxRight - arr[i]; if (diff > maxDiff) { maxDiff = diff; } } } return maxDiff;}X. |
int maxDiff(int arr[], int n){ // Create a diff array of size n-1. The array will hold // the difference of adjacent elements int diff[n-1]; for (int i=0; i < n-1; i++) diff[i] = arr[i+1] - arr[i]; // Now find the maximum sum subarray in diff array int max_diff = diff[0]; for (int i=1; i<n-1; i++) { if (diff[i-1] > 0) diff[i] += diff[i-1]; if (max_diff < diff[i]) max_diff = diff[i]; } return max_diff;}int maxDiff (int arr[], int n){ // Initialize diff, current sum and max sum int diff = arr[1]-arr[0]; int curr_sum = diff; int max_sum = curr_sum; for(int i=1; i<n-1; i++) { // Calculate current diff diff = arr[i+1]-arr[i]; // Calculate current sum if (curr_sum > 0) curr_sum += diff; else curr_sum = diff; // Update max sum, if needed if (curr_sum > max_sum) max_sum = curr_sum; } return max_sum;} |
Brute Force:
int maxDiff(int arr[], int arr_size){ int max_diff = arr[1] - arr[0]; int i, j; for(i = 0; i < arr_size; i++) { for(j = i+1; j < arr_size; j++) { if(arr[j] - arr[i] > max_diff) max_diff = arr[j] - arr[i]; } } return max_diff;} 它的每一个历史最低点都会向后找【所有】历史最高点去比较（你也可以看作是跟每个向后的历史值去比较，只要维护一个maxProfit即可），所以它可以逆向思考，也就是说，遍历到当前点，我们可以向前去比较历史最低点，不断更新
maxProfit，遍历结束总能找到正确值。但需要明确一点，之所以可以这样做，无非两点，之前的信息我们可记录（维护一个最小的
minPrice变量），其次遍历的后向性所带来的好处，由问题本身决定（股票一定是先买后卖）。public int maxProfit(int[] prices) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int i =0;i<prices.length;i++){ if (prices[i] < minprice){ minprice = prices[i]; }else if (prices[i]-minprice > maxprofit){ maxprofit = prices[i] - minprice; } } return maxprofit; }
这是一种思路，带来了
1. 卖的同时可以瞬间买进。（多个操作可以看成一个操作）
2. 没钱的情况下，可以看作向别人借钱（记忆）
虽然代码形式和上一种不太一样，但它们本质上是一种形式，可以互相转换。但该代码的好处在于它更加亲民接地气。更符合人的认知，buy可以看作是借钱的过程，而
max是为了搜索价格最低的买点，sell是维护了最大的利益，而且很重要的一点它是势能突破函数，高一点就向上顶一下，非常形象。buy和sell同时操作price，这是另外一个神奇的地方，因为核心思想提到，卖的同时可以买进，如果只存在一个元素，该操作返回的sell还是为0，可以看作无操作，符合边界条件public int maxProfit(int[] prices) { int buy = Integer.MIN_VALUE; int sell = 0; for (int price : prices){ buy = Math.max(buy, -price); sell = Math.max(sell, buy + price); } return sell; }
它还有另外一种解法，它的买卖同时更加形象。利用的是势能不断增加，突破max就更新max，当价格下降时，势能降低，但最低不超过0。（sum减到0就停止更新）
就从整个prices的价格走势来看，只要有上升的情况，我们就可以使用
sum += prices[i]-prices[i-1]来不断累计（卖的瞬间可以立马买进，多个操作的组合可以看成一个操作）。而当价格走势下降时，处于亏损状态，sum不断减小，而不会取负值。（此处是不会影响max的）。所以维持一个sum很关键，简单总结下，它是个变态势能累积函数（不公平势能累积），上升趋势总能被更新，而下降趋势，下降到0时，不记录势能sum中。好处是把上升趋势的最低点拔高到0势能点，从而可以不断更新较大的max。public int maxProfit(int[] prices) { int sum = 0; int max = 0; for (int i = 1; i < prices.length;i++){ sum = Math.max(0, sum += prices[i]-prices[i-1]); max = Math.max(max, sum); } return max; }
Read full article from LeetCode - Best Time to Buy and Sell Stock | Darren's Blog
