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 1: Input: [7, 1, 5, 3, 6, 4] Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0
In this case, no transaction is done, i.e. max profit = 0.
s思路： 1. 低价买入，高价卖出！从左往右遍历，当遇到开始增加的位置就是可能的低价位，然后遍历后面的高价位，找最大的差值！ 2. 这道题有意思的地方在于：lowprice是目前为止的最小值，后面遇到的值和这个最小值的差值即为目前位置的最大值，两个变量就可以模拟这个动态的过程：lowprice为目前最小值，profit为目前最大profit:而profit=max(profit,prices[i]-lowprice).
class Solution {public: int maxProfit(vector<int>& prices) { // int profit=0; int lowprice=INT_MAX; for(int i=0;i<prices.size();i++){ lowprice=min(lowprice,prices[i]); profit=max(profit,prices[i]-lowprice); } return profit; }};新闻热点
疑难解答
