求数组最大值算法（又是一题动态规划）
求数组最大值算法（又是一题动态规划）//这里少考虑了，前面是负数， 后面又有一个负数，这样会负负得正啊。。。dp[i] = Math.max(dp[i-1]*nums[i] nums[i]);//至少包含一个数字，那就是自己。if(nums.length == 1){return dp[0];//提前结束 }
在线debug
一维dp数组的题目面试必考。我已经写了好多题。 看到这种题目基本想到用动态规划。
再回顾一下动态规划，就是自下向上。先求解子问题。用dp数组保存每一个状态。这里写了一下这题。但是没有ac 100%
class Solution {
public int maxProduct(int[] nums) {
//想到了动态规划。。。
//dp[i] 表示0-i 位置存储最大的值。。。如果没有，就保持num[i]
//子数组是连续的。子序列是可以不连续的。
int dp[] = new int[nums.length];
//dp数组不能默认为0， 这里是相乘。
Arrays.fill(dp 1);
dp[0] = nums[0];
int res = Integer.MIN_VALUE;
for(int i = 1; i< nums.length; i ){
dp[i] = Math.max(dp[i-1]*nums[i] nums[i]);//至少包含一个数字，那就是自己。
res = Math.max(dp[i] res);//放回dp 数组的最大值。
}
return res;
}
}
在线debug
if(nums.length == 1){
return dp[0];//提前结束
}
dp[i] = Math.max(dp[i-1]*nums[i] nums[i]);//至少包含一个数字，那就是自己。
//这里少考虑了，前面是负数， 后面又有一个负数，这样会负负得正啊。。。
// [-2 3 -4] 预期结果：24 但是我的写法只会输出3
class Solution {
public int maxProduct(int[] nums) {
//想到了动态规划。。。
//dp[i] 表示0-i 位置存储最大的值。。。如果没有，就保持num[i]
//子数组是连续的。子序列是可以不连续的。
int dp[] = new int[nums.length];
int dp2[] = new int[nums.length];
//dp数组不能默认为0， 这里是相乘。
Arrays.fill(dp 1);
dp[0] = nums[0];
dp2[0] = nums[0];
if(nums.length == 1){
return dp[0];//提前结束
}
int res = Integer.MIN_VALUE;
for(int i = 1; i< nums.length; i ){
dp[i] = Math.max(dp[i-1]*nums[i] Math.max(nums[i]*dp2[i-1] nums[i]));//至少包含一个数字，那就是自己。
//这里少考虑了，前面是负数， 后面又有一个负数，这样会负负得正啊。。。
// [-2 3 -4] 预期结果：24 但是我的写法只会输出3
dp2[i] = Math.min(dp2[i-1]*nums[i] nums[i]);
res = Math.max(dp[i] res);//放回dp 数组的最大值。
}
return res;//如果只有一个数组。这样放回res == Integer.MIN_VALUE;
}
}
debug修改了一下：
加了一个dp2[i] : 这个用来保存最小值。 就是负数。 然后
dp[i] = Math.max(dp[i-1]*nums[i] Math.max(nums[i]*dp2[i-1] nums[i]));
在这里面选择最大的。有三个值要比较。 这样通过率提高了，但是还不是100%
参考一下大佬的：
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE imax = 1 imin = 1;
for(int i=0; i<nums.length; i ){
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax*nums[i] nums[i]);
imin = Math.min(imin*nums[i] nums[i]);
max = Math.max(max imax);
}
return max;
}
}
// 作者：guanpengchn
// 链接：https://leetcode-cn.com/problems/maximum-product-subarray/solution/hua-jie-suan-fa-152-cheng-ji-zui-da-zi-xu-lie-by-g/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
