public class Solution {
public int MaxProfit(int[] prices)
{
//寻找最优极值点（包括2个端点)
if (prices.Length < )
{
return ;
}
else if (prices.Length == )
{
return prices[] - prices[] > ? prices[] - prices[] : ;
}
else//至少3个点
{
//先对原始数据进行压缩
var list = new List<int>();
for (int i = ; i < prices.Length - ; i++)
{
if (prices[i] != prices[i + ])
{
list.Add(prices[i]);
}
}
var last = list.LastOrDefault();
if (last != prices[prices.Length - ])
{
list.Add(prices[prices.Length - ]);
}
var dic = new Dictionary<int, int>();//记录所有极值点极其类型
//Key是index，Value是类型：-1是极小，1是极大
//list已经压缩，没有平行点了
for (int i = ; i < list.Count - ; i++)
{
//判断是否是极大值点
if (list[i - ] < list[i] && list[i] > list[i + ])
{
dic.Add(i, );
}
else if (list[i - ] > list[i] && list[i] < list[i + ])
{
dic.Add(i, -);
}
//判断是否是极小值点
}
//处理端点
if (dic.Count == )
{
return list[list.Count - ] - list[] > ? list[list.Count - ] - list[] : ;
}
else
{
var list2 = dic.OrderBy(x => x.Key).ToList();
var d1 = list2.FirstOrDefault();
var d2 = list2.LastOrDefault();
if (d1.Value == )
{
list2.Add(new KeyValuePair<int, int>(, -));
}
else
{
list2.Add(new KeyValuePair<int, int>(, ));
}
if (d2.Value == )
{
list2.Add(new KeyValuePair<int, int>(list.Count - , -));
}
else
{
list2.Add(new KeyValuePair<int, int>(list.Count - , ));
}
list2 = list2.OrderBy(x => x.Key).ToList();//得到全部的极值点
var maxProfit = ;
for (int i = ; i < list2.Count; i++)
{
if (list2[i].Value == -)
{
for (int j = i; j < list2.Count; j++)
{
if (list2[j].Value == )
{
if (list[list2[j].Key] - list[list2[i].Key] > maxProfit)
{
maxProfit = list[list2[j].Key] - list[list2[i].Key];
}
}
}
}
}
return maxProfit;
}
}
}
}https://leetcode.com/problems/best-time-to-buy-and-sell-stock/#/description
原来的计算方式太复杂了，使用优化的方式如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minprice = INT_MAX;
int maxprofit = ;
for (int i = ; i < prices.size(); i++)
{
if (minprice > prices[i])
{
minprice = prices[i];
}
else if (prices[i] - minprice > maxprofit)
{
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
};补充一个python的实现：
import sys
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
maxval =
minval = sys.maxsize
for i in range(n):
cur = prices[i]
minval = min(minval,cur)
maxval = max(maxval,cur-minval)
return maxval