dp第六天

「动态规划」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

152. 乘积最大子数组

这题和最大子数组和的区别在于，乘法，负数有机会变成最大。所以两个变量，最大和最小都要保留。另外for循环里面注意小细节：// 防止计算结果参与后续计算 int premax = max; int premin = min;

/**
 152. 乘积最大子数组
 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

 测试用例的答案是一个 32-位 整数。

 子数组 是数组的连续子序列。



 示例 1:

 输入: nums = [2,3,-2,4]
 输出: 6
 解释: 子数组 [2,3] 有最大乘积 6。
 示例 2:

 输入: nums = [-2,0,-1]
 输出: 0
 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。


 提示:

 1 <= nums.length <= 2 * 10^4
 -10 <= nums[i] <= 10
 nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

 * @author zeroheart
 *
 */
public class Question152 {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        // 乘法，最小的乘以nums[i]，可能变成最大的
        int min = nums[0];
        int result = nums[0];
        int len = nums.length;

        if(len==1)return result;

        for(int i=1; i<len; i++){
// 防止计算结果参与后续计算
            int premax = max; int premin = min; 
            max = Math.max(nums[i] * premax, Math.max(nums[i] * premin, nums[i]));
            min = Math.min(nums[i] * premin, Math.min(nums[i] * premax, nums[i]));

            result = Math.max(result, max);
        }

        return result;
    }

    public static void main(String[] args) {

    }
}

1567. 乘积为正数的最长子数组长度

这题也是涉及一个乘法变号的问题。

1567. 乘积为正数的最长子数组长度
 给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

 请你返回乘积为正数的最长子数组长度。



 示例  1：

 输入：nums = [1,-2,-3,4]
 输出：4
 解释：数组本身乘积就是正数，值为 24 。
 示例 2：

 输入：nums = [0,1,-2,-3,-4]
 输出：3
 解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
 注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
 示例 3：

 输入：nums = [-1,-2,-3,0,1]
 输出：2
 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。


 提示：

 1 <= nums.length <= 10^5
 -10^9 <= nums[i] <= 10^9


 * @author zeroheart
 *
 */
public class Question1567 {
    public int getMaxLen(int[] nums) {
        // 这个虽然是dp，但实际上给人不是dp的感觉
        int len = nums.length;
        // 正数长度
        int z = nums[0] > 0 ? 1 : 0;
        // 负数长度
        int f = nums[0] < 0 ? 1 : 0;

        int max = z;


        for(int i = 1; i<len; i++){
            if(nums[i] > 0) {
                z = z + 1;
                f = f > 0 ? f + 1 : 0;
            }else if(nums[i] < 0) {
                // int newz = f > 0 ? f + 1 : 0;
                // int newf = z + 1;
                // z = newz;
                // f = newf;

                int temp = z;
                z = f;
                f = temp;

                z = z > 0 ? z + 1 : 0;
                f = f + 1;
            }else{
                z = 0;
                f = 0;
            }

            max = Math.max(max, z);
        }

        return max;
    }

    public static void main(String[] args) {

    }
}