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; }