昨天去富途面试实习生的时候问到了这样的一道题，记录一下。
题目
求出一串数的最大连乘子序列的乘积。所谓最大连乘子序列，就是指连续的子序列中的乘积最大的那个子序列，比如{-2.5, 3, 0, 2, 4, -6, -2}，2*4*(-6)*(-2)就是乘积最大的连续子序列，结果为96。
思路一
循环暴力破解法，就是穷举所有的子串，然后求出乘积最大的那个，时间复杂度为O(n^2)。
思路二
采用动态规划的思想。
从左到右记录：以某个数 nums[i] 结尾的最小连乘(min_cur)和最大连乘(max_cur)，然后最终选出最大的那个。之所以要记录最小连乘，是因为数字中可能存在负数，当到达一个负数时，乘上上一次的最小连乘才能得出以目前数作为结尾的最大连乘。
最小连乘和最大连乘是从三个值中进行选择，分别是max_cur*nums[i]，min_cur*nums[i])和nums[i]。前两个好理解，第三个是因为有可能不乘上前面的数，自己更大或更小，比如nums[i]是正数，而前面一个数刚好是0，自然就要在这里截断。
代码
代码语言：javascript复制double maxProduct(double nums[], int size){
if(sizeof(nums) == 0) return 0;
double max_cur = nums[0];
double min_cur = nums[0];
double max_final = nums[0];
for(int i = 1; i < size; i ){
double tempMax = max_cur;
double tempMin = min_cur;
max_cur = max(max(tempMax*nums[i], tempMin*nums[i]), nums[i]);
min_cur = min(min(tempMax*nums[i], tempMin*nums[i]), nums[i]);
if(max_cur > max_final){
max_final = max_cur;
}
}
return max_final;
}
