目录
买卖股票的最好时机(一)
访问量:398

一、简介

假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票,并非每天都可以买入或卖出一次,总共只能买入和卖出一次,且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润,请返回0

3.假设买入卖出均无手续费

二、实现

/**
  *  d[i][0] // 代表第i天没持有
  *  d[i][1] // 代表第i天持有
  * @param prices int整型一维数组 
  * @return int整型
*/
func maxProfit( prices []int ) int {
    // write code here
    maxVal := 0
    
    dp := make(map[int]map[int]int)
    dp[0] = make(map[int]int)
    dp[0][0] = 0
    dp[0][1] = 0 - prices[0]
    
    for i:=1; i < len(prices); i++ {
        dp[i] = make(map[int]int)
        
        // 计算当前没持有的最大值
        // 前一天也没持有 或前一天持有今天卖出
        dp[i][0] = getMaxVal(dp[i-1][0],  dp[i-1][1] + prices[i])
        if dp[i][0] > maxVal {
            maxVal = dp[i][0]
        }
        
        // 计算当前持有的最大值
        // 前一天也持有 或前一天没持有今天买入
         dp[i][1] = getMaxVal(dp[i-1][1],   - prices[i])
        if dp[i][1] > maxVal {
            maxVal = dp[i][1]
        }
    }
    
    return maxVal
}


func getMaxVal(n1, n2 int) int {
    if n1 >= n2 {
        return n1
    }
    
    return n2
}