Comments (10)
// 动态规划设dp[i]为以第i个元素结尾的最大乘积,有dp[i]=Math.max(nums[i],nums[i]*dp[i-1]...nums[i]*dp[0]); // 复杂度O(n^2) var maxProduct = function (nums) { var dp = new Array(nums.length).fill(1); for (var i = 0; i < nums.length; i++) { dp[i] = nums[i]; for (var j = i - 1; j >= 0; j--) { dp[i] = Math.max(dp[i], nums[i] * dp[j]); } } return Math.max(...dp); }
这个状态迁移有问题,没有考虑出现负数应该截断,也没有考虑负负得正的情况:
[2,3,-2,4] => 6,[-1,1,2,3,-4] =>24,但你的代码算出来的结果正好相反。
from leetcode.
仔细想了想,这道题不是动态规划。任意N-1个数的乘积,也就是说需要求出每个位置上除自己之外的所有数字的乘积——这也是题目里面说不能用除法的原因,然后取一个最大值。比如:对[2,3,-2,4]做除掉自己之外的乘积得到:[-24,-16,24,-12],最大值24。
from leetcode.
/**
* 动态规划,设dp[i]为以第i个元素结尾的最大乘积,
* 它可能是和dp[j..0](j<i)的最大值或者最小值或者只有它自己构成最大乘积
*
* 所以每次需要dp[i]里记录最大值和最小值
*
* dp[i].max = max(nums[i],nums[i]*dp[i-1..0].max,nums[i]*dp[i-1..0].min)
* dp[i].min = min(nums[i],nums[i]*dp[i-1..0].max,nums[i]*dp[i-1..0].min)
*
* 最后取dp[0..i]中max属性的最大值
*
* 复杂度 O(n^2)
*
* @param {*} nums
* @returns
*/
function maxProduct(nums) {
if (nums.length == 0) return 0;
var dp = new Array(nums.length);
dp[0] = {
max: nums[0],
min: nums[0]
}
var finalMax = nums[0];
for (var i = 1; i < nums.length; i++) {
dp[i] = {
max: nums[i],
min: nums[i]
}
for (var j = i - 1; j >= 0; j--) {
var a = nums[i] * dp[j].max;
var b = nums[i] * dp[j].min;
dp[i].max = Math.max(dp[i].max, a, b);
dp[i].min = Math.min(dp[i].min, a, b);
finalMax = Math.max(finalMax, dp[i].max);
}
}
return finalMax.toFixed(0);
}
from leetcode.
class Solution { public: int maxProduct(vector<int>& nums) { auto maxEnd = nums[0], minEnd = nums[0], maxHere = nums[0], minHere = nums[0], ret = nums[0]; for (auto i = 1; i < nums.size(); ++i) { auto tempMax = nums[i] * maxEnd; auto tempMin = nums[i] * minEnd; maxHere = max(nums[i], max(tempMin, tempMax)); minHere = min(nums[i], min(tempMin, tempMax)); maxEnd = maxHere; minEnd = minHere; ret = max(ret, maxHere); } return ret; } };
你这个是求的连续子序列的最大乘积,它这题是求的不连续的,任意组合。
from leetcode.
class Solution { public: int maxProduct(vector<int>& nums) { auto maxEnd = nums[0], minEnd = nums[0], maxHere = nums[0], minHere = nums[0], ret = nums[0]; for (auto i = 1; i < nums.size(); ++i) { auto tempMax = nums[i] * maxEnd; auto tempMin = nums[i] * minEnd; maxHere = max(nums[i], max(tempMin, tempMax)); minHere = min(nums[i], min(tempMin, tempMax)); maxEnd = maxHere; minEnd = minHere; ret = max(ret, maxHere); } return ret; } };你这个是求的连续子序列的最大乘积,它这题是求的不连续的,任意组合。
嗯。。。删掉删掉
from leetcode.
class Solution { public: int maxProduct(vector<int>& nums) { auto maxEnd = nums[0], minEnd = nums[0], maxHere = nums[0], minHere = nums[0], ret = nums[0]; for (auto i = 1; i < nums.size(); ++i) { auto tempMax = nums[i] * maxEnd; auto tempMin = nums[i] * minEnd; maxHere = max(nums[i], max(tempMin, tempMax)); minHere = min(nums[i], min(tempMin, tempMax)); maxEnd = maxHere; minEnd = minHere; ret = max(ret, maxHere); } return ret; } };你这个是求的连续子序列的最大乘积,它这题是求的不连续的,任意组合。
嗯。。。删掉删掉
这么优雅的代码,别删了,加句话就行:本题解对应https://leetcode-cn.com/problems/maximum-product-subarray/ 此题。 :)
from leetcode.
仔细想了想,这道题不是动态规划。任意N-1个数的乘积,也就是说需要求出每个位置上除自己之外的所有数字的乘积——这也是题目里面说不能用除法的原因,然后取一个最大值。比如:对[2,3,-2,4]做除掉自己之外的乘积得到:[-24,-16,24,-12],最大值24。
嗯嗯。 直观的解法是N^2 , 通过空间换时间,可以到N。 但是还有更多的方法
from leetcode.
领取
from leetcode.
子数组的最大乘积
暴力法
function LSP(list) {
let ret = 1;
let max = -Number.MAX_VALUE;
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
if (i !== j) ret *= list[j];
}
max = Math.max(max, ret);
ret = 1;
}
return max;
}
空间换时间
function LSP(list) {
let ret = 1;
let max = -Number.MAX_VALUE;
const l = [];
const r = [];
l[0] = 1;
r[0] = 1; // useless
r[list.length] = 1;
for (let i = 1; i < list.length; i++) {
l[i] = l[i - 1] * list[i - 1];
}
for (let i = list.length - 1; i >= 1; i--) {
r[i] = r[i + 1] * list[i];
}
for (let i = 0; i < list.length; i++) {
ret *= l[i] * r[i + 1];
max = Math.max(max, ret);
ret = 1;
}
return max;
}
数学分析
function LSP(list) {
let ret = 1;
let smallestPositive = Number.MAX_VALUE;
let smallestPositiveI = -1;
let largestNegative = -Number.MAX_VALUE;
let largestNegativeI = -1;
let firstZeroI = -1;
let missingI = -1;
// 总体的乘积分三种情况
// 正负0
// 如果是0, 找有没有别的0,有的话返回0, 没有的话我们就算下除了这个0之外所有的乘积,然后取它和0的较大值即可。(然而这两个逻辑可以合并)
// 如果是正,那么删除最小的正数即可
// 如果是负数,则说明一定至少有一个负数存在,我们只要知道绝对值最小的负数删除即可
let productAll = 1;
for (let i = 0; i < list.length; i++) {
productAll *= list[i];
if (list[i] === 0 && firstZeroI === -1) {
firstZeroI = i;
}
if (list[i] > 0 && list[i] < smallestPositive) {
smallestPositive = list[i];
smallestPositiveI = i;
}
if (list[i] < 0 && list[i] > largestNegative) {
largestNegative = list[i];
largestNegativeI = i;
}
}
if (productAll > 0) {
missingI = smallestPositiveI;
} else if (productAll < 0) {
missingI = largestNegativeI;
} else {
missingI = firstZeroI;
}
for (let i = 0; i < list.length; i++) {
if (i !== missingI) ret *= list[i];
}
return firstZeroI === -1 ? ret : Math.max(0, ret);
}
from leetcode.
https://mp.weixin.qq.com/s/nb8zwPathjO9p4GCmmGTmQ
from leetcode.
Related Issues (20)
- 树专题中双色标记法后序和前序写反了 HOT 2
- leetcode/thinkings/tree.md 出错 HOT 1
- some error
- 二分查找专题,寻找最左/右插入位置算法模板错误问题 HOT 9
- possible code error in thinkings/heap.md HOT 1
- link error HOT 4
- link is not correct
- [695.最大岛屿面积,360,面试原题]【每日一题】 HOT 3
- 【专题】 反向思考 HOT 3
- 【专题】 考虑每一项对结果到的贡献
- 【专题】递推方程时间复杂度优化
- 已发布文章的代码错误 HOT 7
- Remove duplicate CPP solution and add Python solution for problem 100.same-tree
- Add OSSF Scorecard security workflow
- 题目的排版可否改一改
- 关于二分法中查找中间点索引的算式 HOT 6
- leetcode-thinkings-tree.md BFS 模版调整 HOT 3
- anki-card 中只有10道题吗?截止到2023.11 HOT 1
- 【每日一题】- 2020-xx-xx - xxx
- 大佬,考虑出一个最短路径的专题吗 HOT 6
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from leetcode.