lintcode-191-乘积最大子序列

191-乘积最大子序列

找出一个序列中乘积最大的连续子序列（至少包含一个数）。

样例

比如, 序列 [2,3,-2,4] 中乘积最大的子序列为 [2,3] ，其乘积为6。

标签

子数组 领英 动态规划

思路

在第 i 位中，乘积最大的连续子序列要么是第 i 位数字本身，要么是前 i-1 位的乘积最大的连续子序列与第 i 位的积
只需一次遍历，在遍历时寻找从第 0 位到第 i 位乘积的最大值，但因为会存在负数（负负得正），所以要同时寻找最小乘积，新的数也要乘以最小乘积在进行比较

code

class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: an integer
     */
    int maxProduct(vector<int>& nums) {
        // write your code here
        int size = nums.size();
        if (size <= 0) {
            return 0;
        }
        int maxPro = nums[0], minPro = nums[0], result = nums[0];
        for (int i = 1; i < size; i++) {
            int maxTemp = maxPro, minTemp = minPro;
            maxPro = max(nums[i], max(nums[i] * maxTemp, nums[i] * minTemp));
            minPro = min(nums[i], min(nums[i] * maxTemp, nums[i] * minTemp));
            result = max(result, maxPro);
        }
        return result;
    }
};