原题

LintCode 149. Best Time to Buy and Sell Stock

Description

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.

解题

给出股票价格的变化，只能交易一次，求利润最大值。

直接维护一个当前的最低价和当前的最高利润，遍历一次数组即可。

代码

class Solution {
public:
    /*
    * @param prices: Given an integer array
    * @return: Maximum profit
    */
    int maxProfit(vector<int> &prices) {
        // write your code here
        int ans = 0;
        int minPrice = INT_MAX;
        if (prices.empty()) return ans;
        for (auto i : prices) {
            minPrice = min(minPrice, i);
            ans = max(i - minPrice, ans);
        }
        return ans;
    }
};