冥界152乘积最大子数组
8573 ワード
如果你仔细看看题目就应该直到这道题应该用的是DP思考30分钟后无果,打开题解......
看题解看的一脸懵逼,打开YouTube有人这么解释道:
如果之前的数为10现在是个5那肯定取最后结果50
如果之前的数为-10现在是个-5那也肯定取最后结果为50
如果之前的结果不乘也没有当前的数大,那肯定最后结果为当前的数10000
结果显然,需要前期维护两个数组,マックスアール代表前期プレ计算的结果的最大值,ミンアール代表前期计算结果的最小值,因为你也无法保证当当前的数是正数还是负数.
鉴于上面的思考,写下下面的代码:
看题解看的一脸懵逼,打开YouTube有人这么解释道:
如果之前的数为10现在是个5那肯定取最后结果50
如果之前的数为-10现在是个-5那也肯定取最后结果为50
如果之前的结果不乘也没有当前的数大,那肯定最后结果为当前的数10000
结果显然,需要前期维护两个数组,マックスアール代表前期プレ计算的结果的最大值,ミンアール代表前期计算结果的最小值,因为你也无法保证当当前的数是正数还是负数.
鉴于上面的思考,写下下面的代码:
class Solution {
public:
int maxProduct(vector<int> &nums) {
int size = nums.size();
vector<int> maxarr(size, 0);
vector<int> minarr(size, 0);
maxarr[0] = nums[0];
minarr[0] = nums[0];
for (int i = 1; i < size; i++) {
maxarr[i] = max(max(maxarr[i - 1] * nums[i], minarr[i - 1] * nums[i]), nums[i]);
minarr[i] = min(min(maxarr[i - 1] * nums[i], minarr[i - 1] * nums[i]), nums[i]);
}
return *max_element(maxarr.begin(), maxarr.end());
}
};
当然这里是可以进行优化的,以下のスペースを取ります:int size = nums.size();
vector<int> maxarr(size, 0);
vector<int> minarr(size, 0);
maxarr[0] = nums[0];
minarr[0] = nums[0];
int premax = nums[0];
int premin = nums[0];
int maxres = nums[0];
for (int i = 1; i < size; i++) {
int t = premax;
premax = max(max(premax * nums[i], premin * nums[i]), nums[i]);
premin = min(min(t * nums[i], premin * nums[i]), nums[i]);
maxres = max(maxres, premax);
}
return maxres;
ありがとう!Reference
この問題について(冥界152乘积最大子数组), 我々は、より多くの情報をここで見つけました https://dev.to/iqium/152-cheng-ji-zui-da-zi-shu-zu-in0テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol