假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票,并非每天都可以买入或卖出一次,总共只能买入和卖出一次,且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润,请返回0
3.假设买入卖出均无手续费
数据范围:
要求:空间复杂度 ,时间复杂度
[8,9,2,5,4,7,1]
5
在第3天(股票价格 = 2)的时候买入,在第6天(股票价格 = 7)的时候卖出,最大利润 = 7-2 = 5 ,不能选择在第2天买入,第3天卖出,这样就亏损7了;同时,你也不能在买入前卖出股票。
[2,4,1]
2
[3,2,1]
0
int maxProfit(int* prices, int pricesLen) { if (pricesLen <= 1) return 0; int minPrice = prices[0]; int maxProfit = 0; //从前往后找相对小的值,记录最大的利润 for (int i = 1; i < pricesLen; i++) { if (prices[i] < minPrice)//找价格的较小值买入 minPrice = prices[i]; else if (prices[i] - minPrice > maxProfit)//只有利润更大时才更新 maxProfit = prices[i] - minPrice; } return maxProfit; } //时间复杂度o(n),空间复杂度o(1);
int maxProfit(int* prices, int pricesLen ) { // write code here //MAX用于保存最大利润 int MAX=0; //遍历买入时间 for(int i=0;i<pricesLen;i++) { //遍历卖出时间 for(int j=i+1;j<pricesLen;j++) { //(prices[j]-prices[i])买入卖出利润差 MAX=(prices[j]-prices[i])>MAX?(prices[j]-prices[i]):MAX; } } return MAX; }
#define MAX_BUY 100000 int maxProfit(int* prices, int pricesLen ) { // write code here //保证买入价格最低,卖出价格最高,且买入在卖出之前就可以了 if(prices == NULL || pricesLen <=1) return 0; int buy=MAX_BUY,sell=-1,gain=0; for(int i = 0;i<pricesLen-1;i++) { if(buy>prices[i]) { buy = prices[i]; sell = prices[i+1]; } if(sell<prices[i+1]) sell = prices[i+1]; if(gain<sell - buy) gain = sell-buy; } return gain; }
int maxProfit(int* prices, int pricesLen ) { // write code here int max=0,a=10000,pri=0; //pri记录当前天数卖出时的盈利 max记录最高盈利 a用于存取最低买入价 for(int i=0;i<pricesLen;i++){ if(prices[i]<a) a=prices[i]; //当前价格低于a时,令a=最低买入价 if(prices[i]>a) pri=prices[i]-a; //当前价格高于a时,pri=当天卖出可得盈利 if(pri>max) max=pri; //如果本日卖出盈利>最高盈利,则更新最高盈利 } //根据例子,8 9可以算出9卖出盈利一块,这个时候如果后面递增,则每次都按8买入算。如果后面出现低价,则考虑按这个价格买入的情况下,后续哪个会盈利,因为后续如果出现高价,那么高-当前最低一定大于-之前的最低。如果一路下跌,max就不会更新。 return max; } 一步到位
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param pricesLen int prices数组长度 * @return int整型 * * C语言声明定义全局变量请加上static,防止重复定义 */ int maxProfit(int* prices, int pricesLen ) { // write code here int max = 0; int earn[10000] = {0}; int maxx = 0; for(int i = 0;i<pricesLen;i++){ for(int j = i+1;j<pricesLen;j++){ if(prices[j]>max){ max = prices[j]; } } earn[i] = max-prices[i]; if(earn[i]>maxx){ maxx = earn[i]; } max = 0; } return maxx; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param pricesLen int prices数组长度 * @return int整型 * * C语言声明定义全局变量请加上static,防止重复定义 */ int maxProfit(int* prices, int pricesLen ) { // write code here int i=0,sum=0,max=0; for(i=1;i<pricesLen;i++) { if(sum<0) { sum = prices[i] - prices[i-1]; } else { sum += prices[i] - prices[i-1]; } if(max<sum) max = sum; } return max; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param pricesLen int prices数组长度 * @return int整型 * * C语言声明定义全局变量请加上static,防止重复定义 */ int maxProfit(int* prices, int pricesLen ) { // write code here if(pricesLen == 0) return 0; int sum,sum_max,max,min; sum = sum_max = 0; max = min = prices[0]; for(int i=1; i<pricesLen; i++){ if(prices[i] < min){ //如果产生新的最小值,之前存储的最大值作废 max = min = prices[i]; continue; } if(prices[i] > max){ max = prices[i]; sum = max - min; if(sum > sum_max) sum_max = sum; } } return sum_max; }