这题本来写的自我感觉良好,但是还是挂了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: