LeetCode题解子数组的最大乘积

给定一个长度为N的整数数组,只允许乘法,不能用除法。计算任意 N - 1 个数的组合中乘积最大的一组,并写出算法的时间复杂度。

题解:``` .js
/**
* 动态规划,设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);
}
```

45码

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解统计城市的所有灯泡

这个是我刚毕业的时候,一个真实的面试题,这是一个开放题。题目描述:想办法,将一个城市的所有灯泡数量统计出来。题解:费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里,每套房有灯泡5只,那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡,那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的,具体应…

LeetCode题解黑白圆盘

一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可

LeetCode题解圆上任取三点构成锐角三角形的概率

来自字节跳动的一道几何题题解:1/4

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。