时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M 热度指数:146
本题知识点: 动态规划
算法知识视频讲解

题目描述

假定你知道某只股票每一天价格的变动。
你最多可以同时持有一只股票。但你最多只能进行两次交易(一次买进和一次卖出记为一次交易。买进和卖出均无手续费)。
请设计一个函数,计算你所能获得的最大收益。
示例1

输入

复制
[8,9,3,5,1,3]

输出

复制
4

说明

第三天买进,第四天卖出,第五天买进,第六天卖出。总收益为4。 

备注:

总天数不大于200000。保证股票每一天的价格在[1,100]范围内。