為了求最后的乘積最大梦皮，我們先看看最后的結(jié)果是通過怎樣的比較產(chǎn)生的磺浙。舉個例子nums[3] => nums[0],nums[1],nums[2].
我們有個local的最大和global的最大界逛。global_max即本題結(jié)果也糊。local_max指的是以nums[i] 為結(jié)尾的array的最大乘積，其只有兩種可能：
- nums[i]與之前的local_max 相乘凹髓， 即local_max * nums[i]
- 當(dāng)然叠艳，也可以選擇不與之前的相乘奶陈，即nums[i]
然而本題還要考慮負(fù)數(shù)的情況，則最大值也有可能是local_min * nums[i]得到的附较，同時我們也得維護(hù)local_min , 所以狀態(tài)轉(zhuǎn)移公式如下：
- 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;
}
};
