Leetcode152:乘积最大子数组(动态规划,维护两个状态表)

Leetcode152:乘积最大子数组(动态规划,维护两个状态表)

 

 

 

来源

 1 class Solution {
 2     public int maxProduct(int[] nums) {
 3         int n = nums.length;
 4         int[] maxV = new int[n];
 5         int[] minV = new int[n];
 6         maxV[0] = nums[0];
 7         minV[0] = nums[0];
 8         int res = nums[0];
 9         for(int i = 1; i<n; i++){
10             maxV[i] = Math.max(maxV[i-1] * nums[i],Math.max(minV[i-1] * nums[i], nums[i]));
11             minV[i] = Math.min(minV[i-1]*nums[i], Math.min(maxV[i-1]*nums[i], nums[i]));
12         }
13 
14         //遍历maxV,找到最大的值即为最大乘积
15         for(int i = 0; i<n; i++){
16             res = Math.max(res, maxV[i]);
17         }
18 
19         return res;
20     }
21 }

 

上一篇:poj 1547(水题)


下一篇:CF1553H