[算法] 剑指offer 63 股票最大利润 golang

题目

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

 

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 

限制：

0 <= 数组长度 <= 10^5

解法1: 动态规划

思路

记录股价最小值min,

然后当天最大利润=prices[i]-min

然后记录最大利润或者更新股价最小值即可

代码

//股票最大获利
//记录最小值 min
//当天股票最大获利=prices[i]-min
func maxProfit(prices []int) (respMax int) {
	//参数处理
	if len(prices) == 0 {
		return 0
	}
	min, respMax := prices[0], 0
	for i := 1; i < len(prices); i++ {
		//当天出售最大利润
		currentMax := prices[i] - min
		//更新最大利润
		if currentMax > respMax {
			respMax = currentMax
		} else if prices[i] < min {
			//更新最小利润
			min = prices[i]
		}
	}
	return respMax
}

测试

package main

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

//要点: 动态规划,记录最小值,当天获利最大值=arr[i] - min

func TestP63(t *testing.T) {
	cases := []struct {
		prices []int
		expect int
	}{
		{
			prices: []int{7, 1, 5, 3, 6, 4},
			expect: 5,
		},
		{
			prices: []int{7, 6, 4, 3, 1},
			expect: 0,
		},
	}
	for _, c := range cases {
		actual := maxProfit(c.prices)
		assert.Equal(t, c.expect, actual)
	}
}

image-20220312212846583