今天讲解一道简单的算法题：
- 问题描述
假设我们有一个数组， 数组中按顺序每个元素的值表示当天的股票价格。
例如，数组： [7,1,5] 表示股票第一天是7元，第二天是1元，第三天是5元 约定，只能买一次，卖一次，而且必须是先买后卖。 设计一个算法，找到第几次买和第几次卖，能够实现最大利润。
举例：
输入: [7,1,5,3,6,4]
输出: 5
注解: 第二天买，第5天卖，最大利润是（6-1）：5
不是7-1=6, 因为只能先买后卖。输入: [7,6,4,3,1]
输出: 0
注解: 不能先买后卖，所以利润为0.
- 分析
一、穷举法
遍历数组中的每一项i，然后从数组i+1项开始起每项和第i项相减，计算最大利润。
public class Solution {
public int maxProfit(int prices[]) {
int maxprofit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit)
maxprofit = profit;
}
}
return maxprofit;
}
}时间复杂度： O(n^2) ,循环会跑n(n-1)/2
空间复杂度： O(1)
二、 图标法
对于数组问题，不妨使用图标法，从图表中，找到问题的本质。
如果将数组中每个值放到一个横坐标是时间，纵坐标是价格的图标中来看，问题是否就可以转换为表中尖峰和低谷值之间的差值。
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice)
minprice = prices[i];
else if (prices[i] - minprice > maxprofit)
maxprofit = prices[i] - minprice;
}
return maxprofit;
}
}时间复杂度： O(n) ，只循环一次
空间复杂度： O(1) ；只用了两个变量。
三、动态规划法
public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}