===问:

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4] 输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

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

===答:

根据第一次的经验,直接用range来整~~

此方法一次成功,直接拿下排名第一,赢了100%的对手,关键是算法了!omg

func maxProfit(prices []int) int {
	sum := 0
	for i, price := range prices {
		if i >= 1 && prices[i-1] < price {
			sum += price - prices[i-1]
			fmt.Printf("%v - %v\n", price, prices[i-1])
		}
	}
	return sum
}

// 输入:[7, 1, 3, 5, 6, 4]
// 返回:5
// 计算过程:
// 3 - 1
// 5 - 3
// 6 - 5

方法二:感觉不需要再弄个price了,都用索引吧

func maxProfit(prices []int) int {
	sum := 0
    for i:=1;i<len(prices);i++ {
		if prices[i-1] < prices[i] {
			sum += prices[i] - prices[i-1]
		}
	}
	return sum
}

整个思路。。。嗯~没有!

我只是跟着感觉先写了一个,但说不上对不对,就想着先测试一下,结果每个答案都正确。。。

从这道题就说明算法比写代码重要得多,某些项目知道算法,事半功倍!

===解:

在这里插入图片描述
网上借了张图,简单来说,每次波谷到波峰就是利润最大化,这时候每次循环里的差就是利润,而每次下降就不可能产生利润,被排除在外直到下一个上升期出现。

比如[7,1,5,3,6,4]
索引0排除,1<7排除,5>1计算利润4,3<5利润停止,6<3计算利润3,4排除,这样结果就是4+3=7

比如[1,2,3,4,5]
索引0排除,2>1计算利润1,3>2计算利润1,4>3计算利润1,5>4计算利润1,这样结果就是1*4=4

比如[7,6,4,3,1]
索引0排除,此后所有数字都比前一个小,因此始终没有上升趋势,结果自然为0,无利润。

这道题按照一般的逻辑就需要多次用到循环,先从索引0的值开始与后面循环比较得差值进行判断,再用索引1得值循环与其后比较得值,但这道题实际上我们并不需要真的知道什么时候买,什么时候卖,我们只需要知道利润最大值,因此用这个算法一次循环即可得到答案。

和真的股票买卖还是有差别的,因为你并不知道什么时候该买,什么时候该卖~~哈