长舒一口气, 总算在凌晨之前完成了这道题, 没辜负自己每天一题的承诺. (哄了一天女友的疲惫男人容易么...)
这道题有点难, 难在理解题意. 就像在做项目的时候, 一点也不害怕开发的同事问你问题, 但看见需求的人过来, 就开始头大. 为啥? 你需要花费很长时间, 明白需求到底是什么. 你的脑子里需要有一个完整的"需求分析"的过程. 如果你是软工专业, 一定明白, 最难对付的就是"需求规格说明书"...
这题我亏在一英语很次, 二完全没有财务常识(没炒过股). 但好在我玩过"大富翁", 起码也明白低买高卖才能赚钱...
如何才能获得最大利益? 我想到的就是, 我在最低的时候买, 在最高的时候卖不就行了? 于是我先随手列出测试用例, 看看自己想的对不对:
4 3 6 7 8 9 10 4 6 3 9
最低为3, 最高是10, 赚了7块. 由于题意没有限制交易次数. 所以我在赚了一发之后, 还可以再玩, 开启上帝视角, 我发现 4买6卖, 3买9卖, 又可以再赚两把. 一共是7 + 2 + 6 = 15块. 有规律么? 貌似低买高卖有一个很重要的前提: 这个区间应该是一个从低到高的有序序列!
譬如, 4买为何在6卖? 而不是到9卖? 因为中间有个3 破坏了有序. 4买9卖, 赚5块; 4买6卖加3买9卖, 赚8块. 擦, 我一下子就明白了.
如果基于有序这个前提, 那么我们的题意可以化简为: 找到全部有序子序列, 计算各序列首尾差值, 返回差值总和! (需求分析完成, 业务语言成功的变为了程序员语言. 工作里倒是大部分时间都花在这里了, 笔试题倒是重现了这个场景, 所以这道题不是算法题, 是考察需求分析能力的...)
简化后, 就清楚了, 肯定要遍历, 找到每一个有序子序列, 咋确定? 4 > 3, 不对; 3 < 6, 对了. 抽象一下:
if (v[i] < v[i+1]) // 有序开始.
啥时候结束呢? 遇到不符合条件结束. 然后计算首尾差值, 咦? 首值? 哪还记得啊, 都遍历过去了... 难道要 tmp 记录一下? 太傻了吧. 等等, 我是要计算差值, 既然在遍历, 何不把序列里, 每两个值的差值加和呢!!! Bingo! 大体框架总算出来了:
int profit = 0;
for (auto i = v.begin(); i != v.end(); ++i)
if (*i < *(i+1)) profit += *(i+1) - *i; // 写到这里, 应该发现风险, i+1敢随便用? 判断一下, i+1 != v.end();
return profit;OK, 加了判断差不多了. 想想边界条件? 如果 v是空能行么? 貌似也没问题. 空也过不了判断, 直接返回0了. 提交答案. AC!