一. 问题描述
给定一个整数数组 nums , 找出一个序列中乘积最大的连续子序列 (该序列至少包含一个数).
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6.
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组.
二. 解题思路
本题思路: 采用动态规划的方法进行求解, 找到最优子函数 f(n)=max(f(n-1)*m(n),m(n)), 其中 f(n) 代表前 n 的数中最大值, m(n) 代表第 n 个数的值, 在这里还需要考虑到负数, 所以还需要找到最小值, 因为最小值负数乘以负数可能成为最大值.
步骤一: 设置最小值 min 和最大值 max 初始值.
步骤二: 遍历数组, 比较当前值和当前值乘以最小值以及当前值乘以最大值; 得到新的 min, 和 max, 比较 max 与 temp 的大小, 然后依次遍历数组直到结束, 最后输出 temp.
三. 执行结果
执行用时 :2 ms, 在所有 java 提交中击败了 93.92% 的用户
内存消耗 :37.4 MB, 在所有 java 提交中击败了 35.40% 的用户
四. Java 代码
- class Solution {
- public int maxProduct(int[] nums) {
- int temp=nums[0];
- int min=nums[0];
- int max=nums[0];
- for(int i=1;i<nums.length;i++) {
- int mmin=Math.min(max*nums[i],Math.min(min*nums[i],nums[i]) );
- int mmax=Math.max(min*nums[i], Math.max(max*nums[i], nums[i]));
- min=mmin;
- max=mmax;
- if(max>temp) {
- temp=max;
- }
- }
- return temp;
- }
- }
来源: http://www.bubuko.com/infodetail-3337530.html