描述

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

1. 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2. 如果不能获取到任何利润，请返回0
3. 假设买入卖出均无手续费

数据范围： 0≤ n≤10^5 , 0≤val≤10^4

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例

输入：

// 输入
[8,9,2,5,4,7,1]
// 输出
5
// 说明：在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。 

// 输入
[2,4,1]
// 返回值
2

// 输入
[3,2,1]
// 返回值
0

解题思路

动态规划中贪心算法：找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

• 将每天收入与最低价格相见获取最大值

代码实现

/**
 * [JZ63-简单] 买卖股票的最好时机(一)
 *
 * @param array int 一维数组
 * @return int
 */
func maxProfit(prices []int) int {
    n := len(prices)
    if 0 == n {
        return 0
    }

    min := prices[0]

    ret := 0
    for i := 1; i < n; i++ {
        min = int(math.Min(float64(min), float64(prices[i])))
        ret = int(math.Max(float64(ret), float64(prices[i]-min)))
    }
    return ret
}