题目描述:

假设你有一个数组，其中第i个元素是第i天给定股票的价格。
如果你只被允许完成最多一笔交易(即买入并卖出一股股票)，请设计一个算法来查找最大利润。

• 请注意，在购买之前不能出售股票

Example1

Input: [7,1,5,3,6,4]
Output: 5

Explanation
第二天买入，第五天卖出，利润是6-1=5.

Example 2:

Input: [7,6,4,3,1]
Output: 0

Explanation
在这个例子中，没有交易做成因为最大利润是零

C++输入格式

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
    }
};

范例一

子函数

class Solution {
public:
    int maxProfit(vector<int> &prices) 
    {
        int maxPro = 0;
        int minPrice = INT_MAX;//整型上限 
        for(int i = 0; i < prices.size(); i++)
        {
           minPrice = min(minPrice, prices[i]);
           cout<<minPrice<<" ";
           maxPro = max(maxPro, prices[i] - minPrice);
           cout<<maxPro<<endl;
        }
        return maxPro;
    }
};

main()

int main()
{
    vector<int> vec;
    int i=0;
    int m =0;
    int a[10]={7,1,5,3,6,4};
    for(i=0;i<6;i++)
    {
       vec.push_back(a[i]);
    }

    vector<int>::iterator pos;
    //声明一个迭代器，来访问vector容器。作用:遍历或指向vector容器的元素 
    cout<<"输入数组:";
    for(pos = vec.begin();pos!=vec.end();pos++)
    {
        cout<<*pos<<" ";
    } 
    cout<<endl;
    Solution sol;
    m = sol.maxProfit(vec);
    cout<<m<<endl; 
    return 0;
}

测试结果

测试一

测试二

算法思想

第一步:找到第0天到第i天的最低股价
第二步:找到第0天到第i天可以获得的最大利润
也可以先判断prices[i] 和prices[i - 1]的大小再根据该值选择是找最大利润还是最低股价。
如果prices[i] 大于prices[i - 1]，则最大利润可以刷新，否则最低股价可以刷新。

if(prices[i] > prices[i - 1])
{
       maxPro = max(maxPro, prices[i] - minPrice);
}else{
    minPrice = min(minPrice, prices[i]);
}

另一种方式是判断prices[i] 和prices[i - 1]作减法，若值小于零则置为零否则置为最大值。并且这种方式时间较短

ret += prices[i] - prices[i-1];
cout<<prices[i]<<" ";
cout<<ret<<" "<<endl;
if(ret < 0) ret = 0;
if(ret > max) max = ret;

测试三