寻找乘积最大的连续子序列

[编程题]寻找乘积最大的连续子序列

热度指数：26 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数序列，计算该序列中最大的连续子序列的乘积（该序列至少包含一个数）。

示例1

输入

[2,3,-4,2]

输出

算法知识视频讲解

pein531

使用动态规划，但注意负负得正的情况，防止负负得正之后逆袭正数的连乘，因此需要同时保存连乘过程中能使得结果变大和变小的中间结果。

import java.util.*;


public class Solution {
    /**
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int maxProduct (int[] nums) {
        // write code here
        int tmin = nums[0];
        int tmax = nums[0];
        int result = nums[0];
        for(int i = 1; i < nums.length; i++){
            tmax = Math.max(nums[i], nums[i]*tmax);    // 看是乘了大还是不乘大，不乘大就从nums[i]重新开始
            tmin = Math.min(nums[i], nums[i]*tmin);    // 看是乘了小还是不乘小，不乘小就从nums[i]重新开始
            result = Math.max(result, Math.max(tmax, tmin));
        }
        return result;
    }
}

发表于 2021-02-07 16:15:51 回复(0)