原题地址
https://leetcode.com/problems/maximum-product-subarray/description/
题意
给一个数组，找出能从子数组里得到的最大的乘积。如果数组里只有1个数，则返回这个数。
思路
开了一个维数组dp[n][n]，,dp[i][j]用来表示从原数组的第i个元素到第j个元素的乘积。
dp2[ i ][ 2 ]表示以第i个元素结尾的子数组的最大乘积（0<=i <=n）,dp2[i][0]表示正数，dp2[i][1]表示负数。
代码
1
可以发现dp数组是多余的，删去。如果不删也过不了之后的某个测试样例。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
int dp[n][n];
int dp2[n][2]; //dp2[n][0] store the positive one, and [1] store negative one
for (int i = 0; i < n; i++) {
for (int j = 0; j < n ; j++) {
dp[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
dp[i][i] = nums[i];
if (nums[i] >= 0) {
dp2[i][0] = nums[i];
dp2[i][1] = 1;
} else {
dp2[i][1] = nums[i];
dp2[i][0] = 1;
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j + i < n ; j++) { // 第i个元素到第j个元素这个区间的最大product
int temp1 = nums[j + i] * dp2[j+i-1][0];
int temp2 = nums[j + i] * dp2[j+i-1][1];
if (nums[j + i] >= 0) {
dp[j][j + i] = temp1;
if (temp1 > dp2[j + i][0]) {
dp2[j + i][0] = temp1;
}
if (temp2 < dp2[j + i][1]) {
dp2[j + i][1] = temp2;
}
} else {
dp[j][j + i] = temp2;
if (temp1 < dp2[j + i][1]) {
dp2[j + i][1] = temp1;
}
if (temp2 > dp2[j + i][0]) {
dp2[j + i][0] = temp2;
}
}
}
}
int result = dp2[0][0];
for (int i = i; i < n; i++) {
if (result < dp2[i][0]) result = dp2[i][0];
if (result < dp2[i][1]) result = dp2[i][1];
}
return result;
}
};
2
去掉了多余的二维数组，但是没有考虑到元素为0时的情况，如遇到测试样例
-2,0,-1
期望结果是0，但是会输出1，原因是对dp2的初始赋值操作不当
if (nums[i] >= 0) {
dp2[i][0] = nums[i];
dp2[i][1] = 1;
} else {
dp2[i][1] = nums[i];
dp2[i][0] = 1;
}
把1改为0即可。改了初始赋值操作之后能通过182/283个测试样例，但是在第183个测试样例的时候超时了。
观察发现，实际上并不需要用到两重循环，最外层的循环可以去掉。且对更新dp2的值的算法做了一些小修改，最终得到的代码如下
3
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
int dp2[n][2];
for (int i = 0; i < n; i++) {
if (nums[i] >= 0) {
dp2[i][0] = nums[i];
dp2[i][1] = 0;
} else {
dp2[i][1] = nums[i];
dp2[i][0] = 0;
}
}
int i = 1;
for (int j = 0; j + i < n ; j++) { // 第i个元素到第j个元素这个区间的最大product
if (nums[j + i] == 0) {
dp2[j + i][0] = dp2[j + i][1] = 0;
} else if (nums[j + i] > 0) {
if (dp2[j + i - 1][0] == 0) {
dp2[j + i][0] = nums[j + i];
} else {
dp2[j + i][0] = nums[j + i] * dp2[j + i - 1][0];
}
dp2[j + i][1] = nums[j + i] * dp2[j + i - 1][1];
} else {
dp2[j + i][0] = nums[j + i] * dp2[j + i - 1][1];
if (dp2[j + i - 1][0] == 0) {
dp2[j + i][1] = nums[j + i];
} else {
dp2[j + i][1] = nums[j + i] * dp2[j + i - 1][0];
}
}
}
int result = dp2[0][0];
for (int i = 1; i < n; i++) {
if (result < dp2[i][0]) result = dp2[i][0];
}
return result;
}
};
