[LeetCode] Best Time to Buy and Sell Stock

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.

解题思路

首先设定股票买入价格为prices[0]，遍历整个数组，如果当前元素的值小于买入价格，则将该元素值设为买入价格；如果当前元素值大于等于下一元素值（该值为极大值），则将局部最大值设为当前元素值与买入价格的差值，再将局部最大值与全局最大值进行比较，如果，如果大于全局最大值，则将局部最大值赋给全局最大值。最后得到的全局最大值即为所求。

实现代码1

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/17 22:00
    *  @Status   : Accepted
    *  @Runtime  : 17 ms
******************************************************************/
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() <= 1)
        {
            return 0;
        }
        int max_local = 0;
        int max_global = 0;
        int base = prices[0];
        int i = 0;
        while (i < prices.size() - 1)
        {
            if (prices[i] < base)
            {
                base = prices[i];
            }
            else if (prices[i] >= prices[i + 1])
            {
                max_local = prices[i] - base;
                max_global = max_global > max_local ? max_global : max_local;
            }
            i++;
        }
        max_local = prices[i] - base;
        max_global = max_global > max_local ? max_global : max_local;

        return max_global;
    }
};

实现代码2

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0)
        {
            return 0;
        }

        int max_local = 0;
        int max_global = 0;
        for (int i = 0; i < prices.size() - 1; i++)
        {
            max_local = max(max_local + prices[i + 1] - prices[i], 0);
            max_global = max(max_local, max_global);
        }

        return max_global;
    }
};