为了求最后的乘积最大，我们先看看最后的结果是通过怎样的比较产生的。举个例子nums[3] => nums[0],nums[1],nums[2].
我们有个local的最大和global的最大。global_max即本题结果。local_max指的是以nums[i] 为结尾的array的最大乘积，其只有两种可能：
- nums[i]与之前的local_max 相乘， 即local_max * nums[i]
- 当然，也可以选择不与之前的相乘，即nums[i]
然而本题还要考虑负数的情况，则最大值也有可能是local_min * nums[i]得到的，同时我们也得维护local_min , 所以状态转移公式如下：
- local_max = max { nums[i], local_max * nums[i], local_min * nums[i] }
- local_min = min { nums[i], local_max * nums[i], local_min * nums[i] }
- global_max = max { global_max, local_max }
代码：
// main.cpp
// leetcode
//
// Created by YangKi on 15/11/19.
// Copyright © 2015年 YangKi. All rights reserved.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
using namespace std;
class Solution {
public:
int maxProduct(vector<int>& nums) {
int size = (int)nums.size();
if (size == 0) return 0;
if (size == 1) return nums[0];
int global_max = nums[0];
int local_max = nums[0];
int local_min = nums[0];
for (int i = 1; i <= size - 1 ; i++)
{
int temp_local_max = max(max(local_max * nums[i], nums[i]), local_min * nums[i]);
int temp_local_min = min(min(local_max * nums[i], nums[i]), local_min * nums[i]);;
local_max = temp_local_max;
local_min = temp_local_min;
global_max = max(local_max, global_max);
}
return global_max;
}
private:
int max(int a, int b)
{
return a > b? a : b;
}
int min(int a, int b)
{
return a < b? a : b;
}
};
