首页 > 代码库 > Maximum Product Subarray
Maximum Product Subarray
这题看起来和max subarray差不多，只是加法变乘法，尝试过用分治法，发现划分情况的时候特别麻烦。于是分析下这题本身的特点：
1、对0较敏感，一旦有0，乘积就不变了，所以需要在遇到0 的时候将数组拆分
2、如果没有0， 一旦相乘，绝对值肯定会变大，所以仅考虑正负号的问题就够了。
若整个数组相乘是一个正数，那乘出来的无疑就是最大值，但是乘出来是负数的时候怎么办呢？
思考之下，唯一的办法就是减少一个负数，这时候想到两种情形，要么剪掉最左边的负数，要么剪掉最右边的负数（数组要连续，从两边下手）。
剪掉左边负数的时候，则乘积应从left + 1开始（left是最左边负数的索引）
剪掉右边负数的时候，则乘积应到right -1为止。
不知道是我考虑得太复杂还是实现没想好，我的代码显得不太简洁：
int maxProduct(int A[], int n) { if (n == 1) return A[0]; int i = 0; int result = 0; while (i < n){ int left = -1; int right = -1; int product = 1; while (i < n && A[i] == 0) i++; if (i == n) break; int start = i; while (i < n && A[i] != 0){ product *= A[i]; if (left == -1 && A[i] < 0) left = i; if (A[i] < 0) right = i; i++; } if (product > 0){ if (product > result) result = product; } else { int leftprod = 1; int rightprod = 1; bool flagl = false; for (int index = start; index < right; index++){ leftprod *= A[index]; flagl = true; } bool flagr = false; for (int index = left + 1; index < i; index++){ rightprod *= A[index]; flagr = true; } if (flagl && flagr && max(leftprod, rightprod) > result) result = max(leftprod, rightprod); if (flagl && !flagr) { result = max(leftprod, result); } if (flagr && !flagl) { result = max(rightprod, result); } } } return result;}
Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。