Maximum Product Subarray[难]

这题本来写的自我感觉良好,但是还是挂了edge case。 我本来想的是如果乘上一个数能够增大current continous array, 那就乘,如果会减小,还不如不乘。 这个idea在 Dynamic Programming里算longest increasing sequence非常有用, 但是对于乘法不working。 因为即便current continous array 非常小, -1000. 但是下一个如果是一个负数的话,可以立马把我这个变大。

为了解决这个问题,我增加了一个条件。如果再下一个能把我们变大就乘当前这个,否则当前的就作为下一轮开始的array. 不过这样还是不对, 因为下下个乘上也许就更大了呢。

做到这里真心感叹这道题的变态


答案的idea是,用两个变量: 1. current_continous_max . 2. current_continous_min.

本轮的max product用一个变量储存,如果比max_product大了,就让他变成max_product.

同时我们还一直跟踪continous_min, 为了以防万一哪天小的数乘了什么逆袭。


Followup:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容