解题方法： 1.暴力遍历
一开始我们可以尝试遍历股票的所有价格，比较之后找到利润的最大值，但是这种办法的时间复杂度为O(n^2），在这道题目中会超时，我们可以尝试一下贪心算法和动态规划
代码：int maxProfit(int* prices, int pricesSize)
{
int maxProfit= 0;
int profit = 0;
int i,j;
for(i = 0; i < pricesSize; i++ )
{
for(j = i + 1; j < pricesSize; j++ )
{
profit = prices[j] - prices[i];
maxProfit = fmax(maxProfit, profit);
}
}
return maxProfit;
}
运算结果：
2.贪心算法
我们首先尝试贪心算法，由于股票是先买入再卖出，我们可以在遍历的过程中不断更新前面买入价的最小值，这样只需要用到一重循环，时间复杂度为O（n)
代码：int maxProfit(int* prices, int pricesSize)
{
int maxProfit = 0;
int minPrice =prices[0];
int i;
for(i=0; i< pricesSize; i++)
{
if(minPrice > prices[i])
minPrice = prices[i];
if(prices[i]- minPrice > maxProfit)
maxProfit=prices[i]- minPrice;
}
return maxProfit;
}
运算结果：
3.dp（动态规划）
同样在这道题目中我们也可以采用动态规划，我们首先建立一个二维数组dp[i][j],用i表示天数，用j表示是否持有股票
代码：int maxProfit(int* prices, int pricesSize)
{
int dp[pricesSize][2];
int i;
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(i = 1; i < pricesSize; i++ )
{
dp[i][0] = fmax(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = fmax(dp[i-1][1],-prices[i]);
}
return dp[pricesSize-1][0];
}
运算结果：
知识点： 1.fmax()函数：
fmax()函数是C语言自带的取两个数最大值的函数
