【152】乘积最大子数组

如果你仔细看看题目就应该直到这道题应该用的是DP,思考30分钟后无果,打开题解......

看题解看的一脸懵逼,打开youtube,有人这么解释道:

如果之前的数为10,现在是个5,那肯定取最后结果50

如果之前的数为-10,现在是个-5,那也肯定取最后结果为50

如果之前的结果不乘也没有当前的数大,那肯定最后结果为当前的数10000



结果 结果 结果 结果 结果 前期 前期 个 数 组 组, Maxarr 代表 前期 前期 前期 计算 计算 的 结果 的 的 最 值 值 值 值 值 值 值 值 值 值 值 代表 代表 前期 计算 计算 结果 的 最 小 值 值 值 你 你 也 无法 保证 当 当前 当前 当前 当前 的 数 是 正数 还是 负数 负数.. 也 也 你 你 你 你 你 你

鉴于上面的思考,写下下面的代码:

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;

고맙습니다!