只能够买一卖一次。
不需要用动态规划，遍历一遍数组即可。
DP[i] = prices[i] - min(prices[0], prices[1], …, prices[i])
Result = max(DP[0], DP[1], …, DP[i])
DP[i] 就是从 0 到 i 之间任意一个点买入，在 i 这个点卖出，能够获得的最大收益。
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
min := prices[0]
res := 0
for i := 1; i < len(prices); i++ {
if prices[i] < min {
min = prices[i]
}
curResult := prices[i] - min
if curResult > res {
res = curResult
}
}
return res
}
买卖可以有无数次，但是不能重叠。
这个题目就更简单了，只要第 i 天的大于第 i-1 天的，就买入卖出。
func maxProfit(prices []int) int {
res := 0
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
res += (prices[i] - prices[i-1])
}
}
return res
}
最多可以完成两笔交易。
我们尝试定义状态：
DP[i] 为到第 i 天的最大利润
DP[i-1] 为到第 i-1 天的最大利润
尝试定义状态转移方程：
DP[i] = DP[i-1] + (-a[i]) //买入股票
= DP[i-1] + (a[i]) //卖出股票
那么，这个时候你会发现我们无法判断到底是要买入股票，还是卖出股票。所以这个状态还不够，我们尝试再增加一个维度。
再次尝试定义状态：
DP[i][j]
i 表示数组的下标，表示第 i 天
j 可以为 0 或者 1。
j = 0 表示手上没有股票。
j = 1 表示手上有股票。
DP[i][0] 就是到第 i 天的最大利润，且这时手上没有股票。
DP[i][1] 就是到第 i 天的最大利润，且这时手上有股票。
状态转移方程如下：
DP[i][0] = Max(
DP[i-1][0] //不动，就是在第 i-1 天的时候，手上没有股票。
DP[i-1][1] + a[i] //卖出股票，就是在第 i-1 天的时候，手上有股票。
)
DP[i][1] = Max(
DP[i-1][1] //不动，就是在第 i-1 天的时候，手上有股票。
DP[i-1][0] - a[i] //买入股票，就是在第 i-1 天的时候，手上没有股票。
)
这个时候，这个状态转移方程已经能够解决 121 那个只买卖一次的题目了，DP[n-1][0] 就是买卖一次的最大利润。
但是这个方程中还没有完成 K 笔交易的信息，123 这个题目是完成两笔交易，所以还可能是 4 笔、５ 笔、…。
所以我们再次尝试添加一个新的维度。
再次尝试定义状态：
DP[i][k][j]
i 取值为 0 到 n-1，表示数组的下标，表示第 i 天。（这里 n 就是数组的长度）
j 取值为 0 或者 1。
j = 0 表示手上没有股票。
j = 1 表示手上有股票。
DP[i][0] 就是到第 i 天的最大利润，且这时手上没有股票。
DP[i][1] 就是到第 i 天的最大利润，且这时手上有股票。
k 取值为 0 到 K，表示之前已经交易了多少次。
状态转移方程：
for i := 0; i < n-1; i++ {
for k := 0; k < K; k++ {
DP[i][k][0] = Max (
DP[i-1][k][0] //不动
DP[i-1][k-1][1] + a[i] //卖出一股股票
)
DP[i][k][1] = Max (
DP[i-1][k][1] //不动
DP[i-1][k][0] - a[i] //买入一股股票
)
}
}
最后结果就是
DP[n-1, {0~K}, 0] = Max(
DP[n-1][0][0] //在第 n-1 天，手上没有股票，交易了 0 次。
DP[n-1][1][0] //在第 n-1 天，手上没有股票，交易了 1 次。
...
DP[n-1][K][0] //在第 n-1 天，手上没有股票，交易了 K 次。
)
func maxProfit(prices []int) int {
n := len(prices)
const K int = 2
if n == 0 {
return 0
}
DP := make([][K + 1][2]int, n)
maxint := int(^uint32(0) >> 1)
minint := ^maxint
DP[0][0][0] = 0 //第 0 天，什么也没做
DP[0][0][1] = -prices[0] //第 0 天，买入股票
DP[0][1][0] = minint //no
DP[0][1][1] = minint //no
DP[0][2][0] = minint //no
DP[0][2][1] = minint //no
for i := 1; i < n; i++ {
for k := 0; k <= K; k++ {
if k == 0 {
DP[i][0][0] = DP[i-1][0][0]
} else {
DP[i][k][0] = max(DP[i-1][k][0], DP[i-1][k-1][1]+prices[i])
}
DP[i][k][1] = max(DP[i-1][k][1], DP[i-1][k][0]-prices[i])
}
}
m := DP[n-1][0][0]
for k := 1; k <= K; k++ {
if DP[n-1][k][0] > m {
m = DP[n-1][k][0]
}
}
return m
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
思路见上面一题 123。
func maxProfit(k int, prices []int) int {
n := len(prices)
if n == 0 {
return 0
}
if k > len(prices)/2 { //当 k 特别大的时候，做特殊处理
max := 0
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
max += (prices[i] - prices[i-1])
}
}
return max
}
DP := make([][][2]int, n)
for i := range DP {
DP[i] = make([][2]int, k+1)
}
maxint := int(^uint32(0) >> 1)
minint := ^maxint
DP[0][0][0] = 0 //第 0 天，什么也没做
DP[0][0][1] = -prices[0] //第 0 天，买入股票
for kk := 1; kk < k; kk++ {
DP[0][kk][0] = minint
DP[0][kk][1] = minint
}
for i := 1; i < n; i++ {
for kk := 0; kk <= k; kk++ {
if kk == 0 {
DP[i][0][0] = DP[i-1][0][0]
} else {
DP[i][kk][0] = max(DP[i-1][kk][0], DP[i-1][kk-1][1]+prices[i])
}
DP[i][kk][1] = max(DP[i-1][kk][1], DP[i-1][kk][0]-prices[i])
}
}
m := DP[n-1][0][0]
for kk := 1; kk <= k; kk++ {
if DP[n-1][kk][0] > m {
m = DP[n-1][kk][0]
}
}
return m
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
https://leetcode-cn.com/problems/maximum-product-subarray/
我们先尝试定义状态 DP[i] 为从 0 到 i 中子序列的最大乘积，一定包括第 i 个节点。
那么我们尝试定义状态转移方程： DP[i] = DP[i-1] * nums[i]
如果数组中的数字全部都是正数，那么没有任何问题。
可是 nums[i] 可能是负数，这个时候，方程便无法满足了。
当 nums[i] 为负数的时候，只要 DP[i-1] 也是负数的话，那就有可能是最大乘积，所以同一个节点我们需要同时保存正数和负数。
我们尝试重新定义状态：DP[i][2]，即 DP[i][0] 和 DP[i][1]。
DP[i][0] 表示从 0 到 i 中子序列正的最大乘积
DP[i][1] 表示从 0 到 i 中子序列负的最大乘积
那么状态转移方程如下：
DP[i][0] = if (nums[i] >= 0) //当 nums[i] 是正数
DP[i-1][0]*nums[i] //乘以上一个状态的正数
else //当 nums[i] 是负数
DP[i-1][1]*nums[i] //乘以上一个状态的负数
DP[i][1] = if (nums[i] >= 0)
DP[i-1][1]*nums[i]
else
DP[i-1][0]*nums[1]
DP[i][0] = max(DP[i-1][0]*nums[i], DP[i-1][1]*nums[i], nums[i]) //取正数的最大值
DP[i][1] = min(DP[i-1][1]*nums[i], DP[i-1][0]*nums[1], nums[i]) //取负数中的最小值
最后因为我们需要的是最大的乘积，所以结果就是
Max(DP[0][0], DP[1][0], …, DP[i][0])
/*
状态: DP[i][2]
DP[i][0]:表示从 0 -> i (包括第 i 个节点) 的正的最大值
DP[i][1]:表示从 0 -> i (包括第 i 个节点) 的负的最大值，也就是最小值
DP[i][0] = if (nums[i] >= 0) DP[i-1][0]*nums[i]
else DP[i-1][1]*nums[i]
DP[i][1] = if (nums[i] >= 0) DP[i-1][1]*nums[i]
else DP[i-1][0]*nums[1]
结果： Max(DP[i][0], DP[i-1][0], ..., DP[0][0])
*/
func maxProduct(nums []int) int {
if len(nums) == 0 {
return 0
}
DP := make([][]int, len(nums))
for k := range DP {
DP[k] = make([]int, 2)
}
DP[0][0], DP[0][1] = nums[0], nums[0]
res := DP[0][0]
for i := 1; i < len(nums); i++ {
DP[i][0] = max(DP[i-1][0]*nums[i], DP[i-1][1]*nums[i], nums[i])
DP[i][1] = min(DP[i-1][1]*nums[i], DP[i-1][0]*nums[i], nums[i])
res = max(res, DP[i][0])
}
return res
}
func max(arg ...int) int {
m := arg[0]
for i := 1; i < len(arg); i++ {
if arg[i] > m {
m = arg[i]
}
}
return m
}
func min(arg ...int) int {
m := arg[0]
for i := 1; i < len(arg); i++ {
if arg[i] < m {
m = arg[i]
}
}
return m
}
用滚动数组优化下空间
func maxProduct(nums []int) int {
if len(nums) == 0 {
return 0
}
var DP [2][2]int
DP[0][0], DP[0][1] = nums[0], nums[0]
res := DP[0][0]
for i := 1; i < len(nums); i++ {
x, y := i % 2, (i - 1) % 2
DP[x][0] = max(DP[y][0]*nums[i], DP[y][1]*nums[i], nums[i])
DP[x][1] = min(DP[y][1]*nums[i], DP[y][0]*nums[i], nums[i])
res = max(res, DP[x][0])
}
return res
}
conda update conda
conda update anaconda
conda env list
conda env remove -n env_name
conda create -n hello python=3
source activate hello
source deactivate
通过创建环境的克隆来创建环境的精确副本。这里我们将克隆 snowflakes 创建一个名为 flowers 的精确副本：
conda create --name flowers --clone snowflakes
conda install flask
http://nginx.org/en/docs/http/ngx_http_core_module.html#location
https://blog.51cto.com/fantefei/919431
Syntax: location [ = | ~ | ~* | ^~ ] uri { ... }
location @name { ... }
Default: —
Context: server, location
lsof | grep deleted