leetcode 152 乘积最大子数组
乘积最大子数组
高刷题
class Solution {
public:
int maxProduct(vector<int>& nums) {
int result = 0;
vector<vector<int>> dp(nums.size() , vector<int>(2,0));
dp[0][0] = nums[0]; //最大队列初始化
dp[0][1] = nums[0]; //最小队列初始化
result = dp[0][0];
for(int i=1 ; i<nums.size() ; i++)
{
dp[i][0] = max(dp[i-1][0]*nums[i] , max(nums[i] ,dp[i-1][1]*nums[i] ));
dp[i][1] = min(dp[i-1][0]*nums[i] , min(nums[i] ,dp[i-1][1]*nums[i] ));
if( dp[i][0]> result) result = dp[i][0];
}
return result;
}
};