给定一个数组 prices，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。
你只能抉择 某一天 买入这只股票，并抉择在 将来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例 1：
输出： [7,1,5,3,6,4]
输入： 5
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。
留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输出： prices = [7,6,4,3,1]
输入： 0
解释： 在这种状况下, 没有交易实现, 所以最大利润为 0。
暴力法
写两层 for 循环，一一比拟，必定能比进去，代码就不写了。
工夫复杂度：O(n2)
空间复杂度: O(1)
动静布局
定义子问题
假如咱们曾经晓得 i-1 个股票的最大利润为 dp[i-1]，显然 i 个间断股票的最大利润要么是 dp[i-1]，要么就是 prices[i] - minprice（minprice 为前 i-1 支股票的最小值）。
状态转移方程
dp[i] = Math.max(dp[i-1], prices[i] - minprice)边界条件
dp[0] = 0代码实现
因为咱们在计算 dp[i] 的时候，只关怀 dp[i-1] 与 prices[i]，因而不必把整个 dp 数组保留下来，只需设置一个 max 保留 dp[i-1] 就好了。
public class Solution {public int maxProfit(int[] prices) {
int max = 0;
int minprice = prices[0];
for (int i=1; i<prices.length; i++) {minprice = Math.min(prices[i], minprice);
max = Math.max(max, prices[i] - minprice);
}
return max;
}
}工夫复杂度：O(n)
空间复杂度：O(1)