力扣2874题：动态规划求解最大乘积问题

一、题目解读

力扣2874题要求在一个整数数组中，找到三个不重叠子数组（可为空），使其乘积最大化。需确保子数组不相邻，且乘积结果为正数。当数组长度不足3时，返回0。题目核心在于如何高效划分数组，并计算合法组合的最大乘积。

二、解题思路

使用动态规划策略，解题分为三个关键步骤：

1. 预处理左右最大值数组：分别记录每个位置左侧/右侧的最大元素，确保子数组边界的最优选择；

2. 差值乘积计算：遍历中间位置j，利用左右最大值与当前值之差（left_max[j-1] - nums[j]）与右侧最大值相乘，模拟三个子数组的乘积；

3. 动态更新最大值：遍历过程中实时记录最大合法乘积，并处理乘积为负的情况。

该思路通过空间换时间，避免暴力枚举的O(n^3)复杂度，实现线性时间求解。

三、解题步骤

1. 边界判断：当数组长度n<3时直接返回0，避免无效计算；

2. 预处理left_max数组：从前往后遍历，维护当前位置左侧的最大值（初始为nums[0]）；

3. 预处理right_max数组：从后往前遍历，维护当前位置右侧的最大值（初始为nums[n-1]）；

4. 核心遍历：

○ 对于中间位置j（1<j<n-1），计算(left_max[j-1] - nums[j]) * right_max[j+1]，即左侧最大子数组与右侧最大子数组的差值乘积；

○ 动态更新全局最大值max_val，并确保结果为正（若最大值为负则保留0）。

四、代码与注释

class Solution {

public:

    long long maximumTripletValue(vector<int>& nums) {

        int n = nums.size();

        if (n < 3) return 0; // 边界处理：数组长度不足3时返回0

        // 预处理左边最大值数组

        vector<int> left_max(n);

        left_max[0] = nums[0];

        for (int i = 1; i < n; ++i) {

            left_max[i] = max(left_max[i-1], nums[i]); // 更新左侧最大值

        }

        // 预处理右边最大值数组

        vector<int> right_max(n);

        right_max[n-1] = nums[n-1];

        for (int i = n-2; i >= 0; --i) {

            right_max[i] = max(right_max[i+1], nums[i]); // 更新右侧最大值

        }

        long long max_val = 0;

        // 遍历j，计算差值乘积

        for (int j = 1; j < n-1; ++j) {

            long long current = (long long)(left_max[j-1] - nums[j]) * right_max[j+1];

            // 避免溢出：乘积可能超int范围，需强制转换

            max_val = max(max_val, current);

        }

        return max_val > 0? max_val : 0; // 若最大值负，返回0

    }

};

注释说明：

● 使用long long防止乘积溢出；

● 通过左右预处理数组，直接获取子数组边界的最优值；

● 最终结果需为正数，因此负值情况特判为0。

五、总结

通过动态规划将三维问题降为一维遍历，时间复杂度O(n)，空间复杂度O(n)。核心在于利用预处理数组减少重复计算，确保每个位置只需一次访问即可确定最优解。该思路对类似“不重叠子数组问题”具有通用性，但需注意边界条件与数值溢出的处理。适合作为动态规划入门的典型案例，帮助理解“分治+预处理”的思想。