假设我们有一个包含n个整数的数组,表示单日股票价格。 我们想要找到一对(买入日,卖出日),其中 buyDay ≤ sellDay,并且如果我们在buyDay购买股票并在sellDay卖出,我们将最大化我们的利润。
显然,通过尝试所有可能的(buyDay,sellDay)对并从中选择最好的,可以得到O(n^2)时间复杂度的算法解决方案。 但是,是否存在更好的算法,例如运行时间为O(n)?
假设我们有一个包含n个整数的数组,表示单日股票价格。 我们想要找到一对(买入日,卖出日),其中 buyDay ≤ sellDay,并且如果我们在buyDay购买股票并在sellDay卖出,我们将最大化我们的利润。
显然,通过尝试所有可能的(buyDay,sellDay)对并从中选择最好的,可以得到O(n^2)时间复杂度的算法解决方案。 但是,是否存在更好的算法,例如运行时间为O(n)?
+ (int)maxProfit:(NSArray *)prices {
int maxProfit = 0;
int bestBuy = 0;
int bestSell = 0;
int currentBestBuy = 0;
for (int i= 1; i < prices.count; i++) {
int todayPrice = [prices[i] intValue];
int bestBuyPrice = [prices[currentBestBuy] intValue];
if (todayPrice < bestBuyPrice) {
currentBestBuy = i;
bestBuyPrice = todayPrice;
}
if (maxProfit < (todayPrice - bestBuyPrice)) {
bestSell = i;
bestBuy = currentBestBuy;
maxProfit = (todayPrice - bestBuyPrice);
}
}
NSLog(@"Buy Day : %d", bestBuy);
NSLog(@"Sell Day : %d", bestSell);
return maxProfit;
}
static void findmaxprofit(int[] stockvalues){
int buy=0,sell=0,buyingpoint=0,sellingpoint=0,profit=0,currentprofit=0;
int finalbuy=0,finalsell=0;
if(stockvalues.length!=0){
buy=stockvalues[0];
}
for(int i=1;i<stockvalues.length;i++){
if(stockvalues[i]<buy&&i!=stockvalues.length-1){
buy=stockvalues[i];
buyingpoint=i;
}
else if(stockvalues[i]>buy){
sell=stockvalues[i];
sellingpoint=i;
}
currentprofit=sell-buy;
if(profit<currentprofit&&sellingpoint>buyingpoint){
finalbuy=buy;
finalsell=sell;
profit=currentprofit;
}
}
if(profit>0)
System.out.println("Buy shares at "+finalbuy+" INR and Sell Shares "+finalsell+" INR and Profit of "+profit+" INR");
else
System.out.println("Don't do Share transacations today");
}
def get_max_profit(stock):
p=stock[0]
max_profit=0
maxp=p
minp=p
for i in range(1,len(stock)):
p=min(p,stock[i])
profit=stock[i]-p
if profit>max_profit:
maxp=stock[i]
minp=p
max_profit=profit
return minp,maxp,max_profit
stock_prices = [310,315,275,295,260,270,290,230,255,250]
print(get_max_profit(stock_prices))
public static int maxProfit(List<Integer> in) {
int min = in.get(0), max = 0;
for(int i=0; i<in.size()-1;i++){
min=Math.min(min, in.get(i));
max = Math.max(in.get(i) - min, max);
}
return max;
}
}
function maximizeProfit(array $dailyPrices)
{
$buyDay = $sellDay = $cheaperDay = $profit = 0;
for ($today = 0; $today < count($dailyPrices); $today++) {
if ($dailyPrices[$today] < $dailyPrices[$cheaperDay]) {
$cheaperDay = $today;
} elseif ($dailyPrices[$today] - $dailyPrices[$cheaperDay] > $profit) {
$buyDay = $cheaperDay;
$sellDay = $today;
$profit = $dailyPrices[$today] - $dailyPrices[$cheaperDay];
}
}
return [$buyDay, $sellDay];
}
这是数组中两个元素之间的最大差异,这是我的解决方案:
O(N) 时间复杂度 O(1) 空间复杂度
int[] arr = {5, 4, 6 ,7 ,6 ,3 ,2, 5};
int start = 0;
int end = 0;
int max = 0;
for(int i=1; i<arr.length; i++){
int currMax = arr[i] - arr[i-1];
if(currMax>0){
if((arr[i] -arr[start])>=currMax && ((arr[i] -arr[start])>=(arr[end] -arr[start]))){
end = i;
}
else if(currMax>(arr[i] -arr[start]) && currMax >(arr[end] - arr[start])){
start = i-1;
end = i;
}
}
}
max = arr[end] - arr[start];
System.out.println("max: "+max+" start: "+start+" end: "+end);
在一次面试Facebook解决方案工程师职位的现场编码考试中失败后,我必须在一个冷静的氛围中解决它,这是我的两分钱意见:
var max_profit = 0;
var stockPrices = [23,40,21,67,1,50,22,38,2,62];
var currentBestBuy = 0;
var currentBestSell = 0;
var min = 0;
for(var i = 0;i < (stockPrices.length - 1) ; i++){
if(( stockPrices[i + 1] - stockPrices[currentBestBuy] > max_profit) ){
max_profit = stockPrices[i + 1] - stockPrices[currentBestBuy];
currentBestSell = i + 1;
}
if(stockPrices[i] < stockPrices[currentBestBuy]){
min = i;
}
if( max_profit < stockPrices[i + 1] - stockPrices[min] ){
max_profit = stockPrices[i + 1] - stockPrices[min];
currentBestSell = i + 1;
currentBestBuy = min;
}
}
console.log(currentBestBuy);
console.log(currentBestSell);
console.log(max_profit);
对于多次买入/卖出,请使用以下代码
时间复杂度 O(n)
n=int(input())
a = list(map(int,input().split()))
m=0
b=a[0]
s=0
for i in range(1,n):
if(a[i]<a[i-1]):
s=a[i-1]
m=m+s-b
b=a[i]
if(a[n-1]>b):
m=m+a[n-1]-b
print(m)
def max_profit(arr)
min_arr = []
min_el = arr.first
arr.each do |el|
if el < min_el
min_el = el
min_arr << min_el
else
min_arr << min_el
end
end
max_arr = []
max_el = arr.last
arr.reverse.each do |el|
if el > max_el
max_el = el
max_arr.unshift(max_el)
else
max_arr.unshift(max_el)
end
end
max_difference = max_arr.first - min_arr.first
1.upto(arr.length-1) do |i|
max_difference = max_arr[i] - min_arr[i] if max_difference < max_arr[i] - min_arr[i]
end
return max_difference
end
这段代码应该以O(n)的时间运行,但我认为它会使用大量的空间。
对于所有跟踪最小和最大元素的答案,该解决方案实际上是一个O(n^2)的解决方案。这是因为最后必须检查最大值是否出现在最小值之后。如果没有,就需要进一步迭代,直到满足该条件,这将导致最坏情况为O(n^2)。如果您想跳过额外的迭代,则需要更多的空间。无论哪种方式,与动态编程解决方案相比都不可取。