给定一个数组 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。
提示：
1 <= prices.length <= 105 0 <= prices[i] <= 104
- 确定状态/动作 当前第i天，存在这几个状态， 要么买入状态，要么卖出状态
- 买入： 可以是前面买入，当前持有不变; 可以是今天刚买入
- 卖出： 可以是之前已经卖出，当前不操作； 可以是今天刚卖出
- 定义dp数组、分析dp数组 每一天，都有两种状态可操作, 买入、卖出， 则定义一个二维数组dp[i][j](j <=1)
- dp[i][0]: 当前为买入状态
- dp[i][1]： 当前为卖出状态
- 得出状态转换公式
- dp[i][0]买入，1.中的两个场景 取代价最小的 dp[i][0] = max(dp[i-1][0], -prices[i]) (因为为负值，这里应该取max即成本最小)
- dp[i][1]卖出，1.中的两个场景，取获利最大的dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0]) (后面的是当前卖出的和前天持有之间的利润)
- 初始化
- 第一天dp[0][0] = -prices[0]
- 第一天卖出 情况不存在， 不操作即可获利最大 0
- 验证
func maxProfit(prices []int) int {
//初始dp数组
dp := make([][]int, len(prices))
for k, _ := range dp {
dp[k] = make([]int, 2)
}
//初始化起始
dp[0][0] = -prices[0] //持有
dp[0][1] = 0//卖出
for i:=1; i<len(prices); i++ {
dp[i][0] = max(dp[i-1][0], -prices[i]) //买入时的成本
dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0]) //卖出时的获利
}
return dp[len(prices)-1][1]
}
func max(p1, p2 int) int {
if p1 > p2 {
return p1
}
return p2
}
func min(p1, p2 int) int {
if p1 < p2 {
return p1
}
return p2
}