题目描述
假设你有一个数组，其中第i个元素是股票在第i天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖i出）。请你设计一个算法来计算可以获得的最大收益。
样例
-
示例1
输入：[1,4,2]
返回值：3 -
示例2
输入：[2,4,1]
返回值：2
题目评估
知识点：数组、动态规划
难度：简单
分析
本题我们可以用动态规划一次遍历，时间复杂度O(n)。
遍历的同时记录之前遍历过的数值中最小的股票值，并且每次i++时都计算当前的最大收益值和之前的最大收益值比对，如果本次最大，则记录保存。
Java代码题解
public class Solution {
/**
* @param prices int整型一维数组
* @return int整型
*/
public int maxProfit (int[] prices) {
int minbefore = Integer.MAX_VALUE; // minbefore为遍历时i前面已经遍历过的股票中最低的值
int maxprofit = Integer.MIN_VALUE; // maxprofit为当前位置最大的收益
for (int i = 0; i < prices.length; i++) { // 一次遍历
if(prices[i] < minbefore) { // 首先判断当前股票值是否小于之前所有的股票值中最小的
minbefore = prices[i]; // 如果是，将当前股票值赋值给minbefore
if(prices[i] - minbefore > maxprofit) { // 嵌套if语句计算当前为止的最大收益是否大于maxprofit
maxprofit = prices[i] - minbefore; // 是则将其值赋值给maxprofit
}
} else { // 这里的else语句是外层if语句的配对，如果当前股票值大于前边所有的最小值，执行下边的语句块
if(prices[i] - minbefore > maxprofit) { // 和上个if语句块一样，不给minbefore赋值，只是重新计算maxprofit，即当前最大收益
maxprofit = prices[i] - minbefore; // 如果当前最大收益大于之前的最大收益，则给maxprofit赋值
}
}
}
return maxprofit;
}
public static void main(String[] args) {
Solution s = new Solution();
int res = s.maxProfit(new int[]{1,4,2});
System.out.println(res);
}
}