力扣-买卖股票的最佳时机1

1.问题

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

实例1：

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

实例2：

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

2.说明

1 <= prices.length <= 10^5

0 <= prices[i] <= 10^4

输入说明：

首先输入prices数组元素数目n，然后输入n个整数

输出说明：

输出一个整数

3.范例

输入范例：

6

7 1 5 3 6 4

输出范例：

5

4.思路

方法1：动态规划

最多只能交易1次，每天只有buy和sell两种状态，buy了之后，没有sell之前，不能再buy，且当sell之后则是一直处于卖状态。

当天买的话，则损失  -prices[i]，当天卖的话，则收益  +prices[i] ，当天卖出总收益：buy + prices[i]。

所以我们最后只需要考虑当天买和之前买哪个损失更小，当天卖和之前卖哪个收益更大，所以状态转移方程：

buy = max(buy, -prices[i])  //使用max是因为买的话，是损失，即-prices，选取负数最大，即损失最小

sell = max(sell, buy+prices[i])

边界问题：当第一天买入和卖出时，则buy=-prices[0]，而sell=0。

方法2：贪心算法

贪心算法就是在最低价格买入，在最高价格卖出。当第 i 天时，前 i 天中最低价格买入，buy= min( prices[0] ...prices[i-1])，而第 i 天卖出，则收益= prices[i] - buy ，然后一直取最大的收益。

使用c++正无穷时，需要添加"limits.h"头文件

5.代码

//1.动态规划
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
class Solution
{
public:

    int maxProfit(vector<int> &prices)
    {
        int buy=-prices[0];
        int sell=0;
        for(int i=1;i<prices.size();i++)
        {
            buy=max(buy,-prices[i]);
            sell=max(sell,buy+prices[i]);
        }
        return sell;
    }
};
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    vector<int> prices;
    int data;
    for(int i=0;i<n;i++)
    {
        cin>>data;
        prices.push_back(data);
    }
    int res=Solution().maxProfit(prices);
    cout<<res<<endl;
    return 0;
}

//贪心算法
int maxProfit2(vector<int> &prices)
    {
        int buy=INT_MAX;
        int result=0;
        for(int i=0;i<prices.size();i++)
        {
            if(buy>prices[i])
                buy=prices[i];
            if(result<prices[i]-buy)
                result=prices[i]-buy;
        }
        return result;
    }